Для строки \textbf{S} определим \textbf{Z}-функцию следующим образом: \textbf{Z\[i\] = lcp(S, S\[i..|S|\])}, где \textbf{lcp(S_1, S_2)} равно длине наибольшего общего префикса строк \textbf{S_1} и \textbf{S_2}. Например, для \textbf{S = abacabaa} \textbf{Z}-функция равна \textbf{\[8, 0, 1, 0, 3, 0, 1, 1\]}. Для строки \textbf{S} определим ее префикс-функцию: \textbf{pi\[i\] = max\{k | 0 }≤\textbf{ k }<\textbf{ i, S\[1..k\] = S\[i - k + 1..i\]\}}. Например, для \textbf{S = abacabaa} ее префикс-функция имеет вид: \textbf{\[0, 0, 1, 0, 1, 2, 3, 1\]}. Для некоторой строки \textbf{S} была посчитана ее префикс-функция, а строка \textbf{S} была утеряна. Ваша задача получить ее \textbf{Z}-функцию по заданной префикс-функции. \InputFile В первой строке входного файла содержится натуральное число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{200000}), где \textbf{N} - длина \textbf{S}. Во второй строке записана префикс-функция строки \textbf{S}. \OutputFile Выведите \textbf{N} чисел - искомую \textbf{Z}-функцию.