Beach Volleyball

Vera worked very hard this year and set an example for her colleagues. For March 8th, her reward for excellent service was a long-awaited vacation in a warm country. Her hard working days are over, and Vera is now relaxing on the beach by the Warm Sea.

Vera's favorite hobby is beach volleyball, and she has been waiting a long time to enjoy the excitement of this game. She has already met several nice volleyball players, but she has not yet decided which team deserves such a great player on its roster.

Each of the N team captains wants to get Vera on their team, so each one wants to show off as much as possible. Since everyone wants to play, they agreed on the following rule. All N teams stand in a queue. The first match is played between the two teams at the front of the queue. The winner stays on the court, and the loser goes to the end of the queue. In each following match, the winner of the previous match plays the team at the front of the queue, and the loser again goes to the end of the queue. Each team has a strength, and all strengths are different. The team with the greater strength wins a match. The number of matches can be as large as needed.

Vera decided to follow the fairest principle, a counting-out rhyme. She will play for one of the two teams that play the match with number K. Later she realized she had already chosen a team, and she did not base that choice only on its strength. Vera knows Q such counting-out numbers, each with a different value of K. For each K_i, find which two teams will fight for this valuable prize, that is, which two teams play in match number K_i.

The first line contains one integer N, the number of teams ($2 \le N \le 100000$). The second line contains N different numbers from $1$ to $N$, the strengths of the teams. The first number is the strength of the team at the front of the queue, the second is the strength of the next team, and so on, and the last number is the strength of the team at the end of the queue.

The third line contains one integer Q, the number of counting-out numbers ($1 \le Q \le 100000$). Each of the next Q lines contains one integer K_i ($1 \le K_i \le 10^{18}$), the number of a match Vera is interested in. Note that K_i can be greater than N.

Print Q lines. For the i-th query, print two numbers, the strengths of the two teams that play in match number K_i. The two numbers may be printed in any order.