"Fluttershy, this really isn't Discord's trickery,"$$$\ $$$Twilight Sparkle said to me upon returning from the Canterlot Library. "It's just a group of mischievous magic fairies."
"Magic fairies?"
"They are a pure form of magical beings, capable of freely manipulating natural magic fields to construct external shells. They imitated your appearance to find you, probably just because they really like you."
"Is that so?"$$$\ $$$I glanced at the Fluttershies, and they nodded slightly before emitting a faint glow, blurring our vision.
"It's over now, now that we know all this, but they left behind a puzzle."$$$\ $$$We both watched as they gradually transformed into a group of shining butterflies.
"Let's take a look together."$$$\ $$$The butterflies drifted away in the sunlight, gradually disappearing into the play of light and shadow.
Specifically, the fairies have built $$$n$$$ rectangular pillars of width $$$1$$$ right next to each other on the numbered axes, and the height of the column at position $$$i$$$ is $$$h_i$$$.
In particular, imaginary infinite-height pillars are considered to exist in front of the first pillar and behind the last one, i.e., $$$h_0$$$ and $$$h_{n+1}$$$ are treated as infinite height. Also, no two pillars have the same height.
Next, $$$q$$$ independent queries $$$x,V$$$ are given, indicating that water falls vertically from the infinite height at position $$$x$$$, covering an area of $$$V$$$ units. We need to answer how many of the tops of the pillars were submerged by water after the water flow was complete, i.e., they were covered with water of thickness greater than $$$0$$$.
In particular, for convenience, it is guaranteed that all $$$V$$$ are even.
Water flow: Assume that the water is an ideal fluid and no atmospheric pressure here, so the water always tends to flow to somewhere strictly lower, even when the water is on a horizontal stage. In particular, if the water is on the column surface of some pillars whose height is greater on both sides, the water will equal flow to both sides. Since no two pillars have the same height, this will only happen on the surface of pillar where the water initially falls.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$), representing the number of pillars.
The second line contains $$$n$$$ integers $$$h_1, h_2, ..., h_n$$$ ($$$0 \leq h_i \leq 10^9$$$), representing the heights of the pillars. It is guaranteed that the heights of the pillars are all distinct.
The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \times 10^5$$$), indicating the number of queries.
Following are $$$q$$$ lines, each containing two integers $$$x$$$ and $$$V$$$ ($$$1 \leq x \leq n$$$, $$$2 \leq V \leq 10^9$$$, $$$V$$$ is even), representing the position where the rain falls and the amount of rainfall.
Output $$$q$$$ lines, each containing an integer, representing the answer to each query.
53 2 4 1 533 41 104 4
3 4 2
For the first query of the example, the blue line on the left graph indicates its water level. $$$4$$$ units of water flow equally from position $$$3$$$ to both sides. Eventually, positions $$$1$$$, $$$2$$$, and $$$4$$$ are covered with water, with heights of $$$3.5$$$, $$$3.5$$$, and $$$3$$$, respectively.
For the second query of the example, the blue line on the right graph indicates its water level. Specifically, positions $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$ are covered with a water level of $$$5$$$.
For the third query of the example, the orange line on the right indicates its water level. Specifically, positions $$$2$$$ and $$$4$$$ are covered with water levels of $$$3$$$ and $$$4$$$, respectively. Note that although water has flowed through position $$$3$$$, there is no water accumulation at position $$$3$$$ in the end, so it is not covered.
