锦乐正在练习记忆术，他搭建了一个奇怪的记忆宫殿，其中他定下了 n 个记忆桩子，每个桩子代表一件用于联想的事物，编号从 1 到 n 递增。锦乐的桩子连成一个环，编号为 i(1< i< n) 的桩子与编号为 i-1,i+1 的桩子相连，且编号为 1,n 的桩子也相连，形成闭环

然而锦乐未得精髓，所以当锦乐从编号为 u 桩子出发时，要联想到桩子 v 时，他必须沿着编号递增或递减的方向从 u 在环上一路联想，思绪从一个桩子不断走到相邻的桩子，形成一股记忆流，最终到达 v 。严谨地说，若 (x\bmod n)+1=y ，则 x\to y 是递增顺序的，若 (y\bmod n)+1=x ，则 x\to y 是递减顺序的。因此注意 n > 2 时， 1\to n 属于递减，且 n\to 1 属于递增，特别地 n=2 时 1\to n,n\to 1 既可以递增也可以递减

特别地，对锦乐而言，每个桩子有一个特征系数，编号为 i 的桩子特征系数为 a_i 。沿着记忆流从 x 联想到相邻桩子 y 时，若 a_x\ge a_y ，那么锦乐可以一瞬间从 x 桩子联想到 y；否则联想有困难，此时锦乐需要耗费 a_y-a_x 毫秒才能联想到 y 。当锦乐从环上任一桩子 u 出发寻找 v 时，他的左脑会沿着编号递增方向在环上联想，他的右脑会沿着编号递减方向在环上联想，左右脑同时各自开始联想，想起 v 的时间是左脑记忆流和右脑记忆流中总用时较短的一方

现在锦乐想知道，从任一个桩子 u 开始联想直到想起桩子 v 需要用多少毫秒

首先输入一行两个整数 n,q(2\le n\le10^5,1\le q\le10^5)

接下来输入一行 n 个整数，第 i 个整数代表 a_i(1\le a_i\le10^4)

接下来输入 q 行，每行两个整数 u,v(1\le u,v\le n,u\neq v) ，代表一次询问中联想的起点和终点

输出 q 行，对于每个询问，依次输出一行一个整数代表所用毫秒数