Кислотные дожди

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

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

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

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

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

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

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

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

Первая строка входного файла INPUT.TXT содержит одно целое число n – количество блоков (2 ≤ n ≤ 10⁵).

Во второй строке записано n чисел h₁, ... , h_n (1 ≤ h_i ≤ 10⁹).

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

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

В выходной файл OUTPUT.TXT выведите n−1 чисел – после каждого объединения сегментов выведите емкость получившегося объединенного сегмента.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]