In UMT University's "Algorithms for Strings", students are challenged to transform one string statistic into another. For an unknown string s of length n they are given its Z-function and must reconstruct the corresponding prefix-function (also called the ~π-array~ in KMP). Recall:

• ~Z[i]~ is the length of the longest substring starting at position ~i~ that is also a prefix (the first characters) of ~s~, here we consider the 0-index. Here we consider the proper (strict) substring so at position 0, we have ~Z[0] = 0~ (not taking the entire string). For example: "aaaaaa" - ~[0, 4, 3, 2, 1]~, "aaabaab" - ~[0, 2, 1, 0, 2, 1, 0]~, "abacaba" - ~[0, 0, 1, 0, 3, 0, 1]~.

• ~π[i]~ is the length of the longest proper prefix of the substring ~s[0..i]~ that is also its suffix.

Given all ~Z[i]~, you must output all ~π[i]~.

Input

The first line contains ~a~ single integer ~n~ ~(1 ≤ n ≤ 2 · 10^5)~ - the length of the string.

The second line contains ~n~ space-separated integers ~Z_0, Z_1, . . . , Z_{n-1}~ - the Z-function of the string.

Output

Print ~n~ integers - the prefix-function of the same string, separated by spaces.

Sample Input 1

8
0 0 1 0 3 0 1 1

Sample Ouput 1

0 0 1 0 1 2 3 1

Note: One string s that corresponding to the given Z-function is "ABACABAA".