Arrange Coins

Given several non-negative integers coins. For each n, place coins row by row starting from the first row: row 1 needs 1 coin, row 2 needs 2 coins, and so on. Only completely filled rows count; find the maximum number of rows each n can fill.

输入格式

The first line is the array length N, and the second line contains N integers. Site constraints: 1≤N≤100000, 0≤coins[i]≤10^9.

输出格式

Output N integers, the number of rows each coins[i] can fill, in order.

样例 1

输入：

3
3 4 6

输出：

2 2 3

样例 2

输入：

7
0 1 2 3 5 8 10

输出：

0 1 1 2 2 3 4

样例 3

输入：

2
999999999 1000000000

输出：

44720 44720