锦乐正在练习记忆术，他搭建了一个奇怪的记忆宫殿，其中他定下了 $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$ 行，对于每个询问，依次输出一行一个整数代表所用毫秒数