Longest Contiguous Houses Segment After Each Removal

Initially there are no houses on an integer number line. Build one new house at each coordinate in the order given by queries. After each build, return the number of houses in the longest run of consecutive integer coordinates among all current houses. All build coordinates are guaranteed to be distinct, and the left and right neighbors of a new house's coordinate are never both already occupied. You must return the global longest length after each operation, not the length of the run containing the new house or a list of positions.

输入格式

The first line contains an integer q, and the second line contains q integers queries[i]. 1≤q≤100000, −1000000≤queries[i]≤1000000. Coordinates are distinct; when processed in input order, queries[i]−1 and queries[i]+1 are never both already built. The number line has no extra boundary parameter N.

输出格式

Output one line with q integers: the length of the longest contiguous run of houses after each build, in order.

样例 1

输入：

3
2 1 3

输出：

1 2 3

样例 2

输入：

4
1 3 0 4

输出：

1 1 2 2

样例 3

输入：

3
-1 -2 10

输出：

1 2 2

样例说明

[2,1,3] outputs 1 2 3; [1,3,0,4] outputs 1 1 2 2. The third example [−1,−2,10] is added by this site: the last, isolated house does not change the global maximum length, so the output is 1 2 2.