Find the Good Sequence

Key_logger NSTU ICE Fest Regional Pr...
Limits 1s, 512 MB

Let's say two numbers are called "good" if their difference is at least 2.

Similarly, a sequence is also called good if the sequence is increasing and each adjacent two elements in this sequence are good as well. A sequence must consist of at least 2 elements.

Given an array of length n, For each index i (1 ≤ i ≤ n), print the maximum length of a consecutive good sequence starting from position i.

Input

The first line contains single positive integer n (1 ≤ n ≤ 106) — the number of integers.

Then each of the next ith line contains ith element of the array (0 ≤ array element ≤ 107).

Output

For each index i, print the maximum length of a consecutive good sequence starting from position i.

Sample

InputOutput
7
1 
3 
5 
6 
8
10
11
3
2
0
3
2
0
0

Submit

Login to submit.

Contributors

Statistics

82% Solution Ratio
TahseenEarliest, Jan '20
ishtupeedFastest, 0.1s
QuandrayLightest, 6.9 MB
mdvirusShortest, 217B
Toph uses cookies. By continuing you agree to our Cookie Policy.