Metro Rail Blocks

Limits 1s, 512 MB

The city of Dhaka is experiencing the construction of metro rails. Imagine one such metro rail spans from Gulshan to Mirpur. There will be N blocks in total that will serve as the holding structure for the rail lines. The first block is numbered as 1 and the final block is numbered as N. Construction process is fast and each day, one block is being created. But there is a problem.

The blocks are not constructed sequentially. For example, if N=5, the blocks can be created in the following order: 2,4,5,3,1. Since the orders are random, the construction company wants to keep track of the progress properly. They want to measure how many contiguous blocks are created from the start after each day's work.

You will be given the order of blocks in which they are going to be constructed. You have to answer after each day, how many contiguous blocks are made from the start. The first block is identified as 1.

Input

The first line contains an integer N (N ≤ 1000000), the number of blocks that are going to be constructed. In the next N lines, there will be unique integer from 1 to N, indicating the order of the blocks to be made.

Output

Output N integers, one per line. The i'th integer indicates the number of contiguous blocks are made from the start after the i'th day.

Samples

InputOutput
1
1
1
InputOutput
2
1 2
1
2
InputOutput
3
1 3 2
1
1
3