One day, Rened decided to invite his friends to play a card game. The game consists of a sequence of numbered cards on a table, initially empty. The players take turns adding new cards to the end of this sequence; the $$$i$$$-th player plays the card with value $$$C_i$$$.
The main rule is simple: there cannot be cards with repeated numbers on the table.
Whenever a player plays a card whose number does not appear in the current sequence, it is simply added to the end, extending the sequence normally.
However, if a player plays a card with the same value as another card already on the table, an elimination occurs: all cards from the beginning of the current sequence up to and including the previous card with this value are removed. Then, the newly played card is placed at the end of the sequence. Notice that after this process no repeated values remain on the table, and the sequence is never empty.
To make the game faster, Rened asked you and your team to develop a system that tracks the state of the game and, after each play, reports the largest-value card still on the table and the index of the player who played it.
The input has two lines. The first contains the value of $$$N \ (1 \leq N \leq 2 \times 10^{5})$$$, the number of players. The second contains the card values $$$C_i \ (1 \leq C_i \leq N)$$$.
The output should contain $$$N$$$ lines, each containing two values separated by a space: the value $$$C$$$ of the largest card still on the table and the index $$$i$$$ of the player who played that card.
63 1 4 1 6 6
3 1 3 1 4 3 4 3 6 5 6 6
121 1 4 6 5 8 4 6 8 2 5 2
1 1 1 2 4 3 6 4 6 4 8 6 8 6 8 6 8 9 8 9 8 9 5 11
Explanation for example 1
| 1st play: | 3rd play: | 5th play: |
| Player 1 plays 3 | Player 3 plays 4 | Player 5 plays 6 |
| Cards on the table: [3] | Cards on the table: [3, 1, 4] | Cards on the table: [4, 1, 6] |
| Largest card: 3 (player 1) | Largest card: 4 (player 3) | Largest card: 6 (player 5) |
| 2nd play: | 4th play: | 6th play: |
| Player 2 plays 1 | Player 4 plays 1 | Player 6 plays 6 |
| Cards on the table: [3, 1] | The prefix up to the previous 1 is removed | Cards on the table: [6] |
| Largest card: 3 (player 1) | Cards on the table: [4, 1] | Largest card: 6 (player 6) |
| Largest card: 4 (player 3) |
