C. Уничтожение массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив, состоящий из n неотрицательных целых чисел a1, a2, ..., an.

В этом массиве один за другим зачёркиваются числа. Вам задана перестановка чисел от 1 до n — порядок, в котором это происходит.

После зачёркивания очередного числа вам необходимо найти в этом массиве подотрезок с максимальной суммой, не содержащий ни одного зачёркнутого числа. Сумму чисел в пустом подотрезке считайте равной 0.

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

В первой строке входных данных записано число n (1 ≤ n ≤ 100 000) — длина массива.

В второй строке записаны n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 109).

В третьей строке входных данных записана перестановка чисел от 1 до n — порядок, в котором зачеркиваются числа.

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

В выходной файл выведите n строк, каждая из которых должна содержать одно число — максимальную сумму на подотрезке заданного массива, не содержащем зачёркнутых чисел, после выполнения очередного действия.

Примеры
Входные данные
4
1 3 2 5
3 4 1 2
Выходные данные
5
4
3
0
Входные данные
5
1 2 3 4 5
4 2 3 5 1
Выходные данные
6
5
5
1
0
Входные данные
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6
Выходные данные
18
16
11
8
8
6
6
0
Примечание

В первом тестовом примере происходит следующее:

  1. Зачеркивается третий элемент, массив принимает вид 1 3  *  5. Отрезок с максимально суммой 5 состоит из одного числа 5.
  2. Зачеркивается четвертый элемент, массив принимает вид 1 3  *   * . Отрезок с максимально суммой 4 состоит из двух чисел 1 3.
  3. Зачеркивается первый элемент, массив принимает вид  *  3  *   * . Отрезок с максимально суммой 3 состоит из одного числа 3.
  4. Зачеркивается оставшийся второй элемент, в этот момент непустых допустимых подотрезков не остается, поэтому здесь ответ равен нулю.