Дана последовательность из n целых чисел a1,a2,...,an. Для каждого элемента ak (k=1,2,...,n) мы находим первый элемент правее ak, больший его (если такой существует). Обозначим такой элемент ak1. Затем сделаем то же самое для элемента ak1 и обозначим найденный элемент ak2, и так далее пока последовательность не закончится. Таким образом формируется подпоследовательность ak1,ak2,..., которую мы назовем цепью, начинающейся с индекса k.
Напишите программу, которая выводит для каждого индекса k длину соответствующей цепи, начинающейся с индекса k.
В первой строке записано натуральное число n (0<n≤500000). Во второй строке даны элементы последовательности a1,a2,...,an (0<ai<106).
В одной строке выведите последовательность длин цепей, соответствующих элементам входных данных.