Bico is a ruthless warrior and they slice the creatures that cross their path with his small yet effective knife. Bico however, wants to slice the powerful creatures. If a creature's power is less than the square root of any of the previous creatures' power, Bico does not slice that creature.

Bico raids a dungeon in which there are \(N\) creatures. The creatures are standing in circle form and Bico starts slicing the creatures in the clockwise order. Note that, Bico wants to slay more powerful creatures, so when he faces a creature that he wouldn't slice, he decides to exit the dungeon. Also, the creatures in the dungeon are immortal. Namely, Bico slices the creature and it heals back to full power. This means that Bico can slice a creature more than once.

Bico picks one of the creatures and starts slicing ruthlessly. Can you find the number of creatures Bico can slice for each of the creatures in the circle?

Input

The first line contains \(N\), the number of creatures.

The second line contains exactly \(N\) integers. The \(i\)th number denotes the power of the \(i\)th creature.

• \(1 \leq N \leq 10^5\)
• \(1 \leq A_i \leq 10^9\)

Output

You should print \(N\) numbers in a single line. The \(i^{th}\) number should represent the number of the creatures Bico can slice if they start slicing from \(i^{th}\) creature.

If there are an infinite number of creatures that Bico can slice upon starting from \(i^{th}\), print -1 instead of a number.

Examples

Input:

4
1 2 3 4

Output:

4 3 2 1

Input:

7
36 9 7 8 10 12 5

Output:

6 12 11 10 9 8 7

Input:

5
3 2 2 3 4

Output:

-1 -1 -1 -1 -1

Explanation

1st Input

After starting from the first creature:

• Bico can slice the second creature since it's power is \(2\) and is bigger than \(\sqrt{1}\).
• Bico can slice the third creature since it's power is \(3\) and is bigger than \(\sqrt{2}\).
• Bico can slice the fourth creature since it's power is \(4\) and is bigger than \(\sqrt{3}\).
• Bico has now completed a full circle and facing the creature he has sliced at the start. He cannot slice the first creature since its power is \(1\) and is less than \(\sqrt{4}\). He ends his adventure and slices 4 creatures in total.