Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Metro Rail Blocks

By TarifEzaz · 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

Discussion

Statistics


91% Solution Ratio

bracu_abcEarliest, 6M ago

ProjectDFastest, 0.1s

edge555Lightest, 3.0 MB

sazzatShortest, 313B

Submit

Login to submit