Calculate Truck Distance After Refueling

Vehicle positions are non-decreasing, and vehicles can only move right. Each query independently adds fuel stations at the positions of vehicles a and b, and the position of the last vehicle always has a station; each vehicle stops at the nearest station that is not to its left.

输入格式

The first line contains n q; the second line contains n non-decreasing position values; each of the next q lines contains a b (1-based, a<b). The original gives no value ranges; this site sets 2≤n≤100000, 1≤q≤100000, −10⁹≤position≤10⁹.

输出格式

Output q total distances in query order.

样例 1

输入：

5 1
3 6 10 15 20
2 4

输出：

8

样例 2

输入：

3 1
0 0 5
1 2

输出：

0

样例 3

输入：

3 2
1 2 3
1 3
2 3

输出：

1 1

样例说明

Example 1: the five vehicles travel 3, 0, 5, 0, 0, for a total of 8. Example 2: the first two vehicles already have stations and so does the last vehicle, for a total of 0. Example 3: in both queries only one vehicle moves forward by 1, so the total distances are 1 and 1.