The UWA PCS have decided to organize a pub crawl! However, since this is PCS, they will be doing a pub crawl on a histogram in flatland. This means that the pubs can be described by a 1 dimensional array where every element is the height of the pub. Because the members of the UWA PCS like arbitrary rules, they have decided that they only ever want to travel to pubs in order of strictly increasing height. To help organize the pub crawl, you have been asked to create a program. The pub crawl will work like this. You will be given a 1D array describing \(N\) different pubs, and containing integers that represent the heights of pubs. Then you will get a list of queries. Every query will contain two integers, \(i\) and \(k\). This means the crawl will start at location \(i\) (zero indexed), and you must 'hop pubs' exactly \(k\) times. Hopping to a pub is a well defined process. If you are at some pub, then hopping to a pub means you will go to the first pub to the right (in the histogram) whose height is greater, and if no such pub exists, you will stay where you are.

Input Specification

The first line will contain a two integers, \(N\) and \(Q\) respectively. The next line will contain \(N\) space separated integers, the \(i\)th of which we shall call \(h_i\). These are the heights of the pubs. Following this will be \(Q\) lines each containing a query. A query comprises two space separated integers, \(i\) and \(k\).

Output Specification

For each each query, output a single integer on its own line, the index of the pub after pub hopping \(k\) times from index \(i\) where \(k\) and \(i\) are defined (possibly differently) for each query.

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(1 \leq N,Q \leq 2000\)
• 100 points: \(1 \leq N,Q \leq 100000\)

\(0 \leq i < N\)

\(0 \leq k, h_i \leq N\)

Sample Input

6 2
1 3 2 4 3 5
0 2
1 2

Sample Output

3
5