As a result of the Moriya shrine battle, Suwako had a minor leg injury, and so she had to appoint a knee surgery.
However, Suwako has to wait for $q$ days until then, and she has to leave on a daily basis, crossing some of the $n$ surrounding lined up mountains. More specifically, on the $i$-th day, Suwako needs to travel from the $l_i$-th to the $r_i$-th mountain.
Because of the injury, she can't climb down (she can still climb up somehow). Fortunately, as the Mighty God of Mountains, she can cast a charm on any mountain, raising its height by 1 unit, infinite times, such that the mountain in front of Suwako is **NOT** lower than the mountain she's standing. However, casting a charm will cost energy, so she wants to do it as little as possible. Given the mountains' initial heights, and the schedule for the next $q$ days, help Suwako find the minimum number of times she should cast a charm (pretty please)!
### Input
- The first line consists of 2 integers $n, q$ $(1 \le n, q \le 2 \times 10^5)$ - the number of mountains and scheduled days.
- The second line contains $n$ integers $A_i$ $(1 \le A_i \le 10^9)$ - the heights of the mountains.
- The next $q$ lines, each consists of 2 integers $l_i, r_i$ $(1 \le l_i \le r_i \le n)$, representing the mountain range Suwako needs to cross on the $i$-th day.
### Output
Print $q$ lines, each contains 1 single integer as the answer.
### Example
Input:
```
5 3
2 1 4 2 5
1 4
4 5
2 4
```
Output
```
3
0
2
```
