Степан має \(N\) кульок. На кожній кульці написано ціле число не менше 2. Він буде вставляти їх у циліндр по черзі.

На \(i\)-й кульці записане ціле число \(a_i\). Кулі виготовлені зі спеціального матеріалу. Коли \(k\) кульок, на яких написано \(k\) (\(k \geq 2\)), вишикуються в ряд, усі ці кульки зникнуть.

Для кожного \(i\) (\(1 \leq i \leq N\)) знайдіть кількість кульок після вставки \(i\)-ї кульки.

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 2 \times 10^5\))

Наступний  рядок містить \(N\) цілих чисел \(a_i\) (\(2 \le a_i \le 2 \times 10^5\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(N\) рядків.

\(i\)-й рядок (\(1 \leq i \leq N\)) має містити кількість кульок після вставки \(i\)-ї кульки.

Примітка

До прикладу 1:

Приклад вхідних даних

5
3 2 3 2 2

Приклад вихідних даних

1
2
3
4
3

Приклад вхідних даних

10
2 3 2 3 3 3 2 3 3 2

Приклад вихідних даних

1
2
3
4
5
3
2
3
1
0