409634: GYM103648 K Food Search

As an avid bird keeper, Georgina has placed a series of $$$n$$$ pellets of bird food of varying qualities $$$1$$$ through $$$n$$$ in a line (there is exactly $$$1$$$ pellet of each quality of bird food) for the neighborhood birds to try and enjoy.

Georgina's pellets have been talked about far and wide among the bird community and as a result, she has $$$q$$$ regular birds that frequent her bird feeders in search of good eats. Georgina wants to ensure each of her regulars have enough food, so she wants to calculate how many pellets that each bird will eat.

Each bird arrives at some location, $$$l_i$$$ in the line of food pellets, travels $$$r$$$ pellets forward, eats all pellets that have quality $$$\geq k_i$$$ on the way, and flies away. If $$$l_i$$$ is far enough forward that the bird cannot travel all $$$r$$$ pellets, the bird will fly away after reaching the last pellet. After the bird leaves, Georgina will replace all the pellets that the bird ate.

Help Georgina calculate how many pellets are eaten by each bird!

One of the regular birds

The first line consists of three integers $$$n, q, r$$$ $$$(1 \leq n, q, r \leq 10^5)$$$. The next line consists of $$$n$$$ integers, giving the series of food pellet qualities that Georgina has placed. The next $$$q$$$ lines consist of two integers $$$l_i, k_i$$$ $$$1 \leq l_i, k_i \leq n$$$, which gives the position in the line that the $$$i$$$th bird starts at and the minimum quality food that the $$$i$$$th bird will eat.

For each of the $$$q$$$ bird queries, output the number of pellets that the bird will eat.

5 3 3
4 3 2 5 1
1 2
3 4
2 1

3
1
3

The first bird will eat pellets $$$4, 3, 2$$$. The second bird is quite stingy and will only eat pellet $$$5$$$. The third bird will eat pellets $$$3, 2, 5$$$