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

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

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

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

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

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

Примеры