In this game, there is a sequence of $$$N$$$ cards placed at the center of a table. Each card has a distinct number from $$$1$$$ to $$$N$$$, so the sequence forms a permutation of these values. Each card represents a song in the repertoire, and the number written on it is that song's score, indicating how much the audience likes it.
The festival will have several performance days, and on each day they choose an interval of the sequence, indicating which songs will be available to sing that day. The game is then played considering only this contiguous interval of cards. The singers alternate turns, with Adilson always making the first move. On each turn, the current player must remove exactly one card from the remaining sequence: either the leftmost card or the rightmost card. The removed card represents a song that will be sung by that singer during the show.
Each singer's score is the largest number written among all cards they removed during the game, representing the song by that singer that excited the audience the most. If a singer does not remove any card, their score is $$$0$$$. When all cards have been removed, the singer with the larger score wins. Since all numbers in the sequence are distinct, there is always exactly one winner.
For each given interval, determine which singer wins assuming both play optimally.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N \leq 2 \times 10^{5}$$$, $$$1 \leq Q \leq 2 \times 10^{5}$$$), respectively the number of songs in the repertoire and the number of festival days.
The second line contains $$$N$$$ integers $$$P_1, P_2, \ldots, P_N$$$, a permutation of the integers from $$$1$$$ to $$$N$$$.
For each $$$1 \leq i \leq Q$$$, the $$$i$$$-th of the next $$$Q$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq N$$$), indicating that on that festival day only the songs $$$P_{L_i}, P_{L_i+1}, \ldots, P_{R_i}$$$ will be sung.
For each festival day, print a line containing the name of the winning singer: Reginaldo, if Reginaldo wins, or Adilson, if Adilson wins.
5 32 5 1 4 31 51 12 4
Reginaldo Adilson Adilson
Explanation for example 1
On the first day, all cards are used, and Reginaldo wins when both play optimally. On the second day, there is only card $$$2$$$, which Adilson removes on the first move. On the third day, the cards are $$$5$$$, $$$1$$$, and $$$4$$$, and Adilson can remove card $$$5$$$ immediately.
