CSU本部有校内"小叮当"，其每天的路线都是固定的环形路线，为同学们提供了非常多的方便。
现已知小叮当的路线一共包含N站，编号1~N。
正向行驶的小叮当会按1 -> 2 -> 3 -> ... -> N -> 1的方向行驶，反向会按1 -> N -> N-1 -> ... -> 3 -> 2 -> 1的方向行驶。  
给定所有相邻两站之间小叮当行驶的时间(正向、反向时间相同），假设PIPI要从第X站到第Y站，请你判断是PIPI是乘坐正向还是反向的列车用时更少？

第一行包含两个整数N和M，分别代表校车站数目和询问的次数。
第二行包含N个整数A₁, A₂, ... A_N，其中A_i代表从第i站正向行驶到下一站所用的时间。  
以下M行每行包含两个整数X和Y，代表一个询问。
1 ≤ N, M ≤ 100000  1 ≤ X, Y ≤ N  1 ≤ A_i ≤ 100000

对于每组询问，输出一个整数表示最短时间。

简单 技巧