Knee surgery - MarisaOJ: Marisa Online Judge

Knee surgery

Time limit: 1000 ms
Memory limit: 256 MB
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 ```