Рик превратил себя в кошелёк! Бум! Что вы на это скажете? Вот так поворот! Рик — кошелёк. Что вы на это скажете? Этого не происходило ещё никогда. Рик превратил себя в кошелёк! КОШЕЛЁК-РИК!
Так как Рик теперь не может двигаться, Морти вынужден помогать ему с обратным превращением. Для этого нужно правильным образом добавить в кошелёк несколько купюр. Всего есть n типов купюр, пронумерованных числами от 1 до n так, что чем больше номер купюры, тем больше ее номинал. В кошельке уже лежит некоторая сумма денег: для каждого i от 1 до n в кошельке уже лежит ai купюр этого вида. Более того, купюры лежат там в ряд и отсортированы по номиналу, то есть если в кошельке лежат две купюры типов i и j, где i < j, то купюра типа i расположена левее купюры типа j. Это свойство должно сохраняться в каждый момент: по словам Рика, если его нарушить, последствия будут непредсказуемы!
Благо у Морти есть две изначально пустые стопки sl и sr, в которые он в процесс своих действий может класть купюры.
Кошелёк поддерживает 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 действий: