eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Цепь

Цепь

Лимит времени 3 секунды
Лимит использования памяти 128 MiB

Дана последовательность из n целых чисел a_1, a_2, ..., a_n. Для каждого элемента a_k~(k = 1, 2, ..., n) мы находим первый элемент правее a_k, больший его (если такой существует). Обозначим такой элемент a_{k_1}. Затем сделаем то же самое для элемента a_{k_1} и обозначим найденный элемент a_{k_2}, и так далее пока последовательность не закончится. Таким образом формируется подпоследовательность a_{k_1}, a_{k_2}, ..., которую мы назовем цепью, начинающейся с индекса k.

Напишите программу, которая выводит для каждого индекса k длину соответствующей цепи, начинающейся с индекса k.

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

В первой строке записано натуральное число n~(0 < n \le 500000). Во второй строке даны элементы последовательности a_1, a_2, ..., a_n~(0 < a_i < 10^6).

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

В одной строке выведите последовательность длин цепей, соответствующих элементам входных данных.

Пример

Входные данные #1
10
3 2 4 2 11 2 7 5 8 10
Выходные данные #1
2 2 1 1 0 3 2 2 1 0
Источник 2017 IX International autumn tournament in informatics, Shumen, Junior, День 2, Задача F