On the road leading into the famous tourist city, there is a row of trees planted along the roadside consisting of $n$ trees numbered from $1$ to $n$ from beginning to end of the road, of which the the tree $i$ has height $h_i$. To attract tourists, the city government wants to renovate the trees to make them as attractive as possible. The government offers some plans to choose from. Specifically, for each plans represented by two numbers $L,R$ ,the trees with heights outside the range $[L,R]$ will be eliminated and to consider whether the alternative is possible or not, calculate the total height difference between two consecutive trees to be retained.
Requirement: Given the height of $n$ trees and $q$ plans, compute the total height difference between two consecutive trees remaining in each plan.
### Input
- The first line contains the integers $n,q$ ($1 \le n,q \le 2 \times 10^5$)
- The second line contains $n$ integers $h_i$ $(1 \le h_i \le 10^9)$
- Next is $q$ lines,line $j$ contains two integers $L_j,R_j$ $(1 \le L_j \le R_j \le 10^9)$ describing a plan.
### Output
- For each plan,print the result on one line indicating the total height difference between two consecutive trees that is retained
### Example
Input:
```
5 5
3 1 5 2 4
2 5
1 4
1 3
3 5
4 5
```
Output:
```
7
5
3
3
1
```
### Subtask
- Subtask 1 (20%) : $n,q \le 5000$
- Subtask 2 (20%) : $h_i \le 400$
- Subtask 3 (20%) : $L_j \le L_{j+1},R_j \le R_{j+1}$
- Subtask 4 (20%) : $n,q \le 7 \times 10^4$
- Subtask 5 (20%) : No additional constraints
