Задача . E. Декартово дерево

Ильдар учитель алгоритмов у Вильяма и Харриса. Сегодня, Ильдар рассказывает Декартово дерево. К сожалению, Харрис заболел, поэтому Ильдар учит сегодня только Вильяма.

Декартово дерево это корневое дерево, которое может быть построено с помощью последовательности различных целых чисел. Мы строим декартово дерево следующим образом:

1. Если последовательность пустая, верните пустое дерево;
2. Пусть позиция максимального элемента это \(x\);
3. Удалите элемент на позиции \(x\) из последовательности и разбейте ее на левую и правую часть от этого элемента (которые могут оказаться пустыми) (элемент на самом деле нужно не удалить навсегда, а временно забрать из последовательности);
4. Постройте декартово дерево для каждой части;
5. Сделайте новую вершину для элемента, который был на позиции \(x\), который станет корнем всего дерева. Теперь, если корни декартовых деревьев для левой и правой части существовали, они становятся сыновьями для этой вершины;
6. Верните полученное дерево.

Например, это декартово дерево для последовательности \(4, 2, 7, 3, 5, 6, 1\):

После того, как Ильдар рассказал про декартово дерево, он задал домашнее задание. Он начинает с пустой последовательности \(a\).

В \(i\)-м раунде, он добавляет число \(i\) куда-то в \(a\). Затем, он задает вопрос: чему равна сумма размеров поддеревьев для всех вершин в декартовом дереве текущей последовательности \(a\)?

Вершина \(v\) находится в поддереве вершины \(u\), тогда и только тогда, когда \(v = u\) или \(v\) находится в одном из поддеревьев одного из сыновей вершины \(u\). Размер поддерева вершины \(u\) равен количеству вершин \(v\), таких что \(v\) находится в поддереве вершины \(u\).

Всего Ильдар проведет \(n\) раундов. В качестве домашней работы он просит дать ответ на эти \(n\) вопросов.

На следующий день, Ильдар сказал Харрису, что он тоже должен выполнить это домашнее задание. Харрис получил финальное состояние последовательности \(a\) от Вильяма. К сожалению, у него нету идей как получить ответы на эти \(n\) вопросов. Помогите Харрису!