E. Новое задание
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На 228-й международный турнир по стратегической игре Uzhlyandian Wars было решено установить следующие правило: каждую страну-участницу представляет ровно одна команда из 5 человек.

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

После очередных выборов президента Ужляндии, на которых победил Сергей Александрийский, новый глава государства назначил министром обороны и игровой промышленности генерала Машу. Разумеется, главным приоритетом министра является подсчет боеспособности армии Ужляндии, которая состоит из одной упорядоченной шеренги из n солдат, пронумерованных от 1 до n. Для каждого солдата известно его умение играть в Uzhlyandian Wars: для солдата с номером i умение равно ai.

Было решено, что для участия в турнире будет выбрана команда из трех солдат-игроков и двух солдат-помощников. У игроков умение должно быть равным (для лучшей слаженности команды), а у помощников оно не может быть больше, чем у игроков. Также Маше кажется важным, чтобы один помощник стоял в шеренге левее, а второй — правее всех игроков. Более формально, команда представляет собой пятерку солдат с номерами i, j, k, l, p, так что 1 ≤ i < j < k < l < p ≤ n и ai ≤ aj = ak = al ≥ ap.

Боеспособностью армии является количество различных возможных команд от Ужляндии. Две команды являются различными, если существует такое i, что солдат с номером i является членом первой команды, но не является членом второй.

Но игры играми, а армия должна оставаться армией. Поэтому Маша время от времени отправляет некоторых солдат на боевые учения. В некоторых случаях после них солдаты временно не могут выполнять роль игрока, а иногда после учений солдаты снова могут выполнять роль игрока. Роль помощника солдат может выполнять всегда. До выборов боевых учений не проводилось, то есть изначально все солдаты могут выполнять роль игрока. Маше нужно постоянно контролировать боеспособность Ужляндской армии. Так как Маша генерал, а не программист, она попросила помощи у вас. Вам даны умения солдат, а также данные о результатах учений. После каждого учения вы должны найти количество различных возможных команд по модулю 1000000007 (109 + 7).

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

В первой строке строке входных данных задано единственное целое число n (1 ≤ n ≤ 105) — количество солдат в армии Ужляндии.

Во второй строке задано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — умения игроков.

В третьей строке задано единственное целое число m (1 ≤ m ≤ 105) — количество боевых учений.

В следующих m стоках идет описание учений, каждое задается двумя целыми числами t и x (1 ≤ t ≤ 2, 1 ≤ x ≤ n) в отдельной строке. Если t = 1, то солдат номер x временно не может выполнять роль игрока после этих учений. Если t = 2, то солдат номер x снова может выполнять роль игрока после этих учений.

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

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

Выведите m чисел — количество различных возможных команд после каждого учения.

Ответы нужно выводить по модулю 1000000007 (109 + 7).

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

В первом примере после первых боевых учений можно составить только одну команду с солдатами с номерами [1, 2, 4, 5, 6]. После вторых боевых учений команду можно составить из любых пяти солдат.

Во втором примере после первых боевых учений можно составить только одну команду с солдатами с номерами [1, 2, 3, 7, 8]. После вторых учений можно составить команды с такими номерами солдат: [1, 2, 3, 5, 7], [1, 2, 3, 5, 8], [1, 2, 3, 7, 8], [1, 2, 5, 7, 8], [1, 3, 5, 7, 8], [2, 3, 5, 7, 8]. После третьих учений можно составить команды с такими номерами солдат: [1, 3, 5, 7, 8], [2, 3, 5, 7, 8].