Перестановка — это последовательность длины \(n\) целых чисел от \(1\) до \(n\), в которой все числа встречаются ровно по одному разу. Например, \([1]\), \([3, 5, 2, 1, 4]\), \([1, 3, 2]\) — перестановки, а \([2, 3, 2]\), \([4, 3, 1]\), \([0]\) — нет.
Поликарпу недавно подарили перестановку \(a[1 \dots n]\) длины \(n\). Поликарпу деревья нравятся больше, чем перестановки, поэтому он хочет превратить перестановку \(a\) в корневое бинарное дерево. Массив различных целых чисел он превращает в дерево следующим образом:
- максимальный элемент массива становится корнем дерева;
- все элементы слева от максимума — образуют левое поддерево (которое строится по тем же правилам, но применяемым для левого участка массива), но если слева от максимума элементов нет, то у корня нет левого сына;
- все элементы справа от максимума — образуют правое поддерево (которое строится по тем же правилам, но применяемым для правого участка массива), но если справа от максимума элементов нет, то у корня нет правого сына.
Например, если он строит дерево по перестановке \(a=[3, 5, 2, 1, 4]\), то корнем будет элемент \(a_2=5\), левым поддеревом будет дерево, которое будет построено для подмассива \(a[1 \dots 1] = [3]\), а правым — для подмассива \(a[3 \dots 5] = [2, 1, 4]\). В итоге будет построено следующее дерево:
Дерево, соответствующее перестановке \(a=[3, 5, 2, 1, 4]\). Другой пример: пусть перестановка имеет вид \(a=[1, 3, 2, 7, 5, 6, 4]\). В этом случае дерево выглядит так:
Дерево, соответствующее перестановке \(a=[1, 3, 2, 7, 5, 6, 4]\). Обозначим за \(d_v\) глубину вершины \(a_v\), то есть количество ребер на пути от корня до вершины с номером \(a_v\). Заметьте, что глубина корня равна нулю. По заданной перестановке \(a\) для каждой вершины найдите значение \(d_v\).