Задача: Кислотные дожди

Для сборки лаборатории-поселения на Венеру доставлены \(n\) блоков. Блоки расположены в ряд, \(i\)-й блок имеет высоту \(h_i\).

Сборку будет осуществлять специальный робот. В процессе сборки последовательные сегменты блоков будут постепенно объединяться. При этом порядок блоков в ряду не будет меняться.

Исходно каждый блок представляет собой отдельный сегмент, сегменты пронумерованы от \(1\) до \(n\) в том же порядке, что и блоки. Если есть два соседних сегмента, составленных из блоков: сегмент из блоков \(A = [i, i+1, \ldots, i+p-1]\) и сегмент из блоков \(B = [i+p, i+p+1, \ldots, i+p+q-1]\), то после их объединения в один получается сегмент \(AB = [i, i+1, \ldots, i+p-1, i+p, i+p+1, \ldots, i+p+q-1]\).

Инструкция по сборке состоит из \(n-1\) инструкций. Каждая инструкция характеризуется одним числом, \(j\)-я инструкция характеризуется числом \(k_j\). После выполнения этой инструкции сегменты с номерами \(k_j\) и \(k_j + 1\) объединяются в один, получившийся сегмент занимает место в последовательности сегментов на месте двух объединенных сегментов, и вводится новая нумерация на сегментах в том порядке, в котором они расположены — номера сегментов, начиная с \(k_j + 2\), уменьшаются на один. После выполнения всех инструкций все сегменты окажутся объединены в один общий сегмент.

На Венере постоянно идут кислотные дожди, поэтому в процессе сборки важно для каждого сегмента блоков понимать, сколько жидкости может скопиться в этом сегменте. Пусть сегмент состоит из блоков высотой \(h_l, h_{l+1}, \ldots, h_r\). Для \(p\), где \(l \le p \le r\) определим глубину блока c высотой \(h_p\) в этом сегменте следующим образом. Посчитаем величины \(l_p = \max \{ h_l, \ldots, h_p \}\), \(r_p = \max \{ h_p, \ldots, h_r\}\). Это самые высокие блоки в сегменте слева и справа от \(p\)-го. Тогда глубина блока \(p\) в его сегменте равна \(d_p = \min(l_p, r_p) - h_p\), заметим, что \(d_p \ge 0\). Емкостью сегмента будем называть сумму глубин блоков этого сегмента, то есть \(w = d_l + d_{l+1} + \ldots + d_r\).

Задана последовательность объединений сегментов. После каждого объединения выведите емкость получившегося сегмента.

Рисунок на следующей странице показывает процесс выполнения инструкции из примера, над каждым блоком указана его глубина, а для нового сегмента показана его емкость.

Формат входных данных
Первая строка содержит одно целое число \(n\) — количество блоков (\(2 \leq n \leq 10^5\)).

Во второй строке записано \(n\) чисел \(h_1, \ldots, h_n\) (\(1 \leq h_i \leq 10^9\)).

В третьей строке записаны \(n - 1\) чисел — инструкции по объединению сегментов. Каждая инструкция характеризуется одним числом \(k_j\) (\(1 \leq k_j \leq n - j\)).

Формат выходных данных
Выведите \(n-1\) чисел — после каждого объединения сегментов выведите емкость получившегося объединенного сегмента.

Ваш ответ: