This is the hard version of the problem. The only difference between the two versions is the constraint on $$$x$$$. In this version, $$$x$$$ could be up to $$$10^5$$$.
It's raining cats and corgis! ... and a whole bunch of other random animals.
As a zoology-meteorology-geology triple major, you immediately rush to the field to study the phenomenon. The field is an array of $$$N$$$ positions, where the $$$i^{th}$$$ position has elevation $$$h_i$$$.
As you observe the unusual precipitation of animals, you notice that the animals fall from the sky and stack on top of each other. Each animal adds $$$1$$$ unit of elevation to the position where it lands. Animals continue to stack on top of each other until all valleys in the landscape are filled. Formally, a valley exists if there exist positions $$$i, j, k$$$ such that $$$1 \leq i \lt j \lt k \leq N$$$ and $$$h_i \gt h_j \lt h_k$$$ (Visual example provided below).
You wonder that if you increase the height of the landscape at position $$$i$$$ by $$$x$$$ units, how many animals will fill the resulting landscape.
The first line of input contains 2 space-separated integers $$$N, Q \ (1 \leq N, Q \leq 10^5) - $$$ the size of the landscape and the number of queries to process, respectively.
The second line of input contains $$$N$$$ integers $$$h_i \ (0 \leq h_i \leq 10^5)$$$ separated by spaces, representing the initial elevation at the $$$i^{th}$$$ position in the landscape array.
Each of the following $$$Q$$$ lines contains two integers $$$p_i \ (1 \leq p_i \leq N)$$$ and $$$x_i \ (1 \leq x_i \leq 10^5)$$$, representing the position in the landscape array where the elevation will be increased by $$$x$$$ units.
Note: The changes made in each query should be preserved and taken into account when processing subsequent queries.
Please output $$$Q$$$ lines, where the $$$i^{th}$$$ line contains the answer to the $$$i^{th}$$$ query.
10 42 1 4 4 5 2 3 4 5 33 17 14 15 1
8 7 6 6
5 40 5 0 5 02 14 13 11 1
5 6 5 5
6 20 0 0 0 0 02 14 1
0 1
