Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

Задача B. MEXI

Аза решал следующию задачу от Нархана:

Вам задан массив $a$, состоящий из $n$ целых неотрицательных чисел.

Назовем разделение массива $a$ на $k$ отрезков $(l_1, r_1), . . . ,(l_k, r_k) x-$ хорошим, если выполняются следующие условия:

• Каждый элемент массива $a$ принадлежит ровно одному отрезку.

• Для каждого $1 \leq i \leq k$, $MEX$ чисел $(a_{l_i}, . . . , a_{r_i})$ был меньше или равен $x$.

В этой задаче $MEX$ некоторого массива — это минимальное неотрицательное целое число, которое не содержится в этом массиве. Например:

• $MEX$ для $[2, 2, 1]$ равен 0, поскольку 0 не принадлежит массиву.

• $MEX$ для $[3, 1, 0, 1]$ равен 2, поскольку 0 и 1 принадлежат массиву, а 2 — нет.

• $MEX$ для $[0, 3, 1, 2]$ равен 4, поскольку 0, 1, 2 и 3 принадлежат массиву, а 4 — нет.

Размером $x$ хорошего разделение является количество отрезков на которое оно было разделено — то есть $k$.

Вам нужно для каждого целого числа $x$ от $0$ до $n − 1$ вывести минимальный возможный размер $x$ хорошего разделения, если данное разделение невыполнимо выведите $−1$.

Формат входного файла

Первая строка содержит одно целое число — $n (1 \leq n \leq 10^6)$.

Вторая строка содержит $n$ целых чисел $a_1, a_2, . . . , a_n (0 \leq a_i \leq 10^6)$ — массив $a$.

Формат выходного файла

Выведите $n$ целых чисел, где $i$-е число — это минимальный возможный размер $x$ хорошего разделения при $x = i − 1$, если данное разделение невыполнимо выведите $−1$.

Система оценки

Примеры

Вход

4
0 1 0 2

Выход

-1 3 2 1

Вход

1
2

Выход

1