Randy is playing his favorite game: Dino Run.
Dino run is situated on a circular map with positions $$$1$$$ to $$$n$$$. At any given time, a position could be empty or filled with a cactus. The Dino moves right at a constant pace of $$$1$$$ position per timestep; when the Dino is at position $$$N$$$, it arrives at position $$$1$$$ at the next timestep. The game is over when the Dino touches a cactii.
Initially, all the positions are empty, and every timestep, a cactus grows at an empty position. If a cactii grows in a position in the same timestep that the Dino is on that position, the game is over.
Randy controls this Dino, and has one action he can make: jump. In a single jump, the Dino leaps into the air and floats for up to the next $$$k$$$ timesteps. In other words, the Dino can jump over at most $$$k$$$ consecutive cactii. Note that while the Dino is in the air, it still moves forward at the constant rate of one position per timestep.
Since Randy is a pro gamer, his jumps are precisely powered and timed. However, given the growth of the cactii, at some point, it is inevitable that the game will be over. To help Randy calculated his trajectories, he gives you $$$q$$$ queries.
For each query, he gives you a starting point $$$l$$$ and an ending point $$$r$$$. He wants to find the last possible timestep his Dino can start on the ground (not floating) at position $$$l$$$ and successfully end on the ground (not floating) at position $$$r$$$ without losing.
Please help Randy so he can set the new high score.
The first line contains $$$n, k, q$$$. $$$1 \leq k \lt n \leq 10^6, 1 \leq q \leq 10^5$$$.
The second line contains $$$n$$$ integers, $$$c_1, c_2, c_3, ... c_n$$$, where $$$c_i$$$ is the location where a cactus is added at the $$$i$$$th timestep. $$$1 \leq c_i \leq n$$$. Note that the second line represents the order that the cactii are added, not the timestep in which each position gets filled.
The next $$$q$$$ lines contain two integers each $$$l, r$$$, which represent the range for each query. $$$1 \leq l,r \leq n$$$. Note that it is not guaranteed that $$$l \lt r$$$. If $$$r \lt l$$$, it means that we are considering the trajectory on the map going from position $$$r, r+1, ..., n, 1, 2, ..., l-1, l$$$.
Output $$$q$$$ integers, one for each query, representing the first time when it is impossible for a dino to go from $$$l$$$ to $$$r$$$. Output $$$-1$$$ for a query if it is just generally impossible.
10 2 2 7 9 1 3 2 6 4 10 5 8 10 5 7 7
2 -1
4 0 10 4 3 2 1 1 4 1 3 1 2 1 1 2 4 2 3 2 2 3 4 3 3 4 4
-1 -1 1 3 -1 -1 2 -1 1 -1
For the first query in the first sample, the section we are interested in the trajectory of positions $$$10, 1, 2, 3, 4, 5$$$.
If Randy starts at $$$10$$$ at timestep $$$2$$$, Randy performs a small jump, causing us to be in the air at timestep $$$3$$$ and touch down at timestep $$$4$$$ at position $$$2$$$. Then, at timestep $$$4$$$, Randy immediately jumps again causing us to be in the air for timestep $$$5$$$ and timestep $$$6$$$, landing at position $$$5$$$ safely at timestep $$$7$$$.
If instead Randy starts at timestep $$$3$$$ notice that he would land at position $$$2$$$ at timestep $$$5$$$, but there would already be a cactus there, causing him to lose.
Therefore, timestep $$$2$$$ is the latest timestep that Randy can complete this segment.
For the second query in the first sample, this is impossible since a cactus spawns at position $$$7$$$ at timestep $$$1$$$, and the Dino needs to start and end on the ground. So, the Dino can never spawn, causing this to be impossible.
