N. Number of Steps
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Diogo is a child who loves to play by jumping on the steps of the park's staircase in his city. Each step of the staircase has a light, and Diogo enjoys jumping on the steps that are illuminated. He always jumps every $$$K$$$ steps where $$$K$$$ is greater than $$$1$$$, as he does not like to climb the stairs like everyone else normally does by stepping on every step. In other words, if we number the steps starting from $$$1$$$, Diogo will land on steps $$$K$$$, $$$2K$$$, $$$3K$$$, and so on.

Diogo always tries to find out the number $$$K$$$ that will allow him to jump on the largest number of illuminated steps. Therefore, he asked for your help to develop a program that calculates the maximum number of illuminated steps he can jump on.

Initially, all the step lights are off, and you will receive a list of numbers indicating which steps will toggle the state of its light in order. For each operation of toggling the light of a step, your program must respond with the maximum number of lights Diogo can step on by choosing the best possible $$$K$$$ to jump every $$$K$$$ steps $$$(K \gt 1)$$$.

Input

The first line contains an integer $$$N$$$ indicating the number of light operations $$$(1 \leq N \leq 10^5)$$$. The second line contains $$$N$$$ integers $$$D_i$$$ indicating in order the number of the step that will toggle the state of its light, either turning it off or on $$$(2 \leq D_i \leq 10^6)$$$.

Output

For each light operation, you should print a line with the maximum number of illuminated steps that Diogo can step on if he jumps every $$$K$$$ steps for some $$$K$$$ greater than $$$1$$$.

Examples
Input
6
2 4 6 2 15 9
Output
1
2
3
2
2
3
Input
4
3 5 25 50
Output
1
1
2
3