Кошелёк
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рик превратил себя в кошелёк! Бум! Что вы на это скажете? Вот так поворот! Рик — кошелёк. Что вы на это скажете? Этого не происходило ещё никогда. Рик превратил себя в кошелёк! КОШЕЛЁК-РИК!

Так как Рик теперь не может двигаться, Морти вынужден помогать ему с обратным превращением. Для этого нужно правильным образом добавить в кошелёк несколько купюр. Всего есть n типов купюр, пронумерованных числами от 1 до n так, что чем больше номер купюры, тем больше ее номинал. В кошельке уже лежит некоторая сумма денег: для каждого i от 1 до n в кошельке уже лежит ai купюр этого вида. Более того, купюры лежат там в ряд и отсортированы по номиналу, то есть если в кошельке лежат две купюры типов i и j, где i < j, то купюра типа i расположена левее купюры типа j. Это свойство должно сохраняться в каждый момент: по словам Рика, если его нарушить, последствия будут непредсказуемы!

Благо у Морти есть две изначально пустые стопки sl и sr, в которые он в процесс своих действий может класть купюры.

Кошелёк поддерживает 4 вида операций:

  1. Вынуть из кошелька самую левую купюру и положить её с правого края стопки sl.
  2. Вынуть из кошелька самую правую купюру и положить её с левого края стопки sr.
  3. Вставить с левого края кошелька новую купюру.
  4. Вставить с правого края кошелька новую купюру.

После каждой операции третьего или четвёртого типа необходимо тут же возвратить все вынутые купюры в кошелёк, а именно — все купюры стопки sl, не меняя их расположения, поместить в левый край кошелька, а sr — в правый край. В самом начале стопки sl и sr пустые.

Чтобы превратить Рика из кошелька назад в человека, Морти должен по очереди поместить в кошелёк m новых купюр, j-я добавленная купюра должна быть типа bj. Купюры должны быть добавлены операциями 3-го и 4-го видов. После каждой операции купюры должны оставаться отсортированными по номиналу слева направо. Рик и Морти, чтобы понять, сколько времени у них займёт этот процесс, обратились к вам за помощью. Напишите программу, которая определит, какое наименьшее число операций первого и второго типов потребуется непосредственно перед каждым добавлением очередной купюры.

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

Первая строка входных данных содержит число n — количество различных типов купюр (1 ≤ n ≤ 105).

Вторая строчка содержит n целых числел ai — изначальное количество купюр каждого типа, которые лежат в кошельке (0 ≤ ai ≤ 105).

В третьей строке находится число m — количество купюр, которые надо добавить в кошелёк, чтобы Рик обратно превратился в человека (1 ≤ m ≤ 2·105).

В последней строке входных данных находится m чисел bj — типы купюр, которые надо добавить в кошелёк, что бы Рик снова стал человеком (1 ≤ bj ≤ n).

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

В первой строке выходных данных выведите через пробел количество операций первого и второго типа, которое надо будет совершить перед каждым добавлением очередной купюры в кошелёк.

Пример

Входные данные
3
2 3 2
5
2 1 2 3 2
Выходные данные
2 0 2 0 3 

Примечание

Будем изображать текущее положение в формате sl / s / sr, где s — последовательность купюр, лежащих в кошельке.

В первом тесте в самом начале ситуация выглядит как  / 1122233 / , после чего осуществляется 5 действий:

  1. Чтобы добавить купюру типа 2, надо с любой из сторон дважды взять купюру, потом с той же стороны засунуть купюру типа 2.
  2. В  / 11222233 /  добавить купюру типа 1 можно, просто засунув эту купюру с левой стороны.
  3. Из  / 111222233 /  быстрее всего вынуть два раза купюру справа, получить  / 1112222 / 33 и добавить справа купюру типа 2.
  4. В  / 1112222233 /  сразу добавляем справа купюру типа 3.
  5. Нет разницы, с какой стороны в  / 1112222333 /  три раза вынуть купюру. Например, слева: получим 111 / 2222333 /  и добавим слева купюру типа 2, получив финальную ситуацию  / 11122222333 / .