Nested Dolls Stacking

Marc is teaching kindergarten children and has chosen nesting dolls to introduce the concept of size. Each doll has a size denoted by \(a\). Doll \(y\) can be nested inside doll \(x\) if their sizes \(a_x\) and \(a_y\) satisfy \(a_x - a_y \ge 2\). The dolls can be nested multiple layers deep.

The process spans \(n\) days. On the \(i\)-th day, Marc buys a doll of size \(a_i\). After each day, determine the maximum number of dolls that can be nested using the dolls purchased so far.

Note: You can reorder the dolls arbitrarily when forming the nesting chain, but each doll may be used at most once.

inputFormat

The first line contains an integer \(n\) \( (1 \le n \le 10^5)\) representing the number of days.

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\) representing the sizes of the dolls purchased on each day.

outputFormat

Output \(n\) lines, where the \(i\)-th line contains a single integer representing the maximum number of dolls that can be nested using the dolls purchased up to day \(i\).

sample

5
5 3 4 2 1

1
2
2
2
3