Problem Description

Snuke, who has become an oil king, deeply loves gasoline and never fails to use a car for moving within the kingdom.
The kingdom has $ N $ gas stations, and the $ i $th gas station sells gasoline for $ V_i $ yen per liter.

Additionally, the gas stations are lined up in a straight line from the 1st to the $ N $th, and moving between the $ i $th and $ j $th gas stations requires $ |i-j| $ liters of gasoline.

Now, Snuke plans to visit gas stations for $ Q $ days.

On the $ i $th day, he plans to go from the $ S_i $th to the $ T_i $th gas station. To do this, he will pass through several gas stations, and at each stop, even if it is his destination, he will pay and fill his car to the full tank. Moreover, he must always stop at his destination, but he does not necessarily have to stop at the gas stations on the way, and he can freely choose which gas stations to stop at.

Since Snuke's driver, Sumeke, cannot prevent him from refueling, he decided to investigate which gas stations to stop at to minimize the cost of moving between the target gas stations.

So, it's your turn. For each day, find the minimum amount of money Snuke will use.

Note that it is guaranteed that the car is full of gasoline before each day's trip, and Snuke's car will never run out of gasoline during any travel between gas stations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ V_1 $ $ V_2 $ ... $ V_N $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ ... $ S_Q $ $ T_Q $

• The first line contains the number of gas stations $ N(1≦N≦4000) $ and the number of days of Snuke's trips $ Q(1≦Q≦200,000) $.
• The next line contains $ N $ integers, where the $ i $th integer represents the price of gasoline per liter at the $ i $th gas station $ V_{i}(1≦V_{i}≦100,000) $.
• The following $ Q $ lines contain two integers each, where the $ i $th line contains the starting gas station $ S_{i}(1≦S_{i}≦N) $ and the destination gas station $ T_{i}(1≦T_{i}≦N) $ for the $ i $th day, separated by a space. It is guaranteed that $ S_{i}≠T_{i} $.

Output Format

Output the minimum amount of money required for the travel on the $ i $th day on the $ i $th line.

Sample Input and Output

Sample Input #1

3 3
5 3 4
3 1
1 2
2 1

Sample Output #1

8
3
5

Notes/Hints

Scoring

There are no partial points for this problem.

Sample Explanation 1

Sample Explanation 2

Sample Explanation 3

Note that sometimes it may be better to take a detour.

见题面 Input 部分

见题面 Output 部分