Преобразование строковых функций

Для строки S определим Z-функцию следующим образом: Z[i] = lcp(S, S[i..|S|]), где lcp(S_1, S_2) равно длине наибольшего общего префикса строк S_1 и S_2. Например, для S = abacabaa Z-функция равна [8, 0, 1, 0, 3, 0, 1, 1].

Для строки S определим ее префикс-функцию: pi[i] = max{k | 0 ≤ k < i, S[1..k] = S[i - k + 1..i]}. Например, для S = abacabaa ее префикс-функция имеет вид: [0, 0, 1, 0, 1, 2, 3, 1].

Для некоторой строки S была посчитана ее Z-функция, а строка S была утеряна. Ваша задача получить ее префикс-функцию по заданной Z-функции.

Входные данные

В первой строке входного файла содержится натуральное число N (1 ≤ N ≤ 200000), где N - длина S. Во второй строке записана Z-функция строки S.

Выходные данные

Выведите N чисел - искомую префикс-функцию.

Примеры