Get Min Connection Cost

Warehouse capacities are in non-decreasing order. Warehouse i connects to the nearest hub j with j not less than i, at cost capacity[j]−capacity[i]. Warehouse n is always a hub. Each query independently adds two hubs, hubA and hubB; output the total connection cost. The source example's 13 is wrong; by the definition, the correct cost is 5.

输入格式

The first line contains n q (3≤n≤200000, 1≤q≤200000); the second line contains n non-decreasing capacities (1..10⁹); each of the next q lines contains A B, with 1≤A<B<n.

输出格式

Output q integers in query order.

样例 1

输入：

5 1
1 2 4 6 9
1 3

输出：

5

样例 2

输入：

3 1
1 1 1
1 2

输出：

0

样例 3

输入：

4 2
1 3 6 10
1 2
2 3

输出：

4 2

样例说明

Example 1: the hubs are 1, 3 and 5; the warehouse costs are 0, 2, 0, 3, 0, for a total of 5. Example 2: all capacities are equal, so the cost is 0. Example 3: with hubs 1, 2 and 4, only warehouse 3 pays 10−6=4; with hubs 2, 3 and 4, only warehouse 1 pays 3−1=2.