Card Bundles

There are N cards, and each integer from 1 through N is written on exactly one card. The cards are shuffled into a row. For N = 6, one arrangement could be:

[6] [3] [2] [1] [4] [5]

At first, each single card is its own bundle, so there are N card bundles in order.

A bundle is valid if the card numbers inside it consist only of consecutive integers. For example, [2], [4 5], and [3 5 6 4] are valid bundles.

You may merge two adjacent bundles when the newly formed bundle is also valid. Repeating this operation N - 1 times can make all cards into one bundle. One possible merge sequence is shown below.

[6] [3] [2] [1] [4] [5][6] [3] [2 1] [4] [5][6] [3 2 1] [4] [5][6] [3 2 1] [4 5][6] [3 2 1 4 5][6 3 2 1 4 5]

Given the initial arrangement of the N cards, output a sequence of N - 1 merges that turns all cards into one valid bundle. The input is guaranteed to allow such a sequence. If several sequences are possible, output any one of them.

The first line contains an integer N (1 <= N <= 500,000).

The second line contains N integers, separated by spaces, representing the initial card arrangement in order.

Print N - 1 lines. Each line contains one integer describing one merge.

When merging two adjacent bundles, print the original position of the last card in the front bundle. For example, in [6] [3 2 1] [4 5], if the front bundle [3 2 1] is merged with the back bundle [4 5], the last card of the front bundle is 1, which was the fourth card in the initial arrangement, so print 4.