Мальчик Петя очень любит игрушечных солдатиков. У него есть n солдатиков, причем i-ый солдатик покрашен в цвет ai.
Так как Пете постоянно не нравится, как раскрашены его солдатики, он целых m раз выбирал кого-нибудь из них и перекрашивал. Мальчик Вова, наблюдавший за этим, заинтересовался, после какой по счету перекраски все солдатики впервые стали одинакового цвета. Помогите Вове ответить на его вопрос.
В первой строке записано единственное целое число n (1 ≤ n ≤ 105) — количество солдатиков у Пети.
Во второй строке через пробел записаны n целых чисел a1, ..., an (1 ≤ ai ≤ 109) — исходные цвета, в которые были раскрашены солдатики.
В третьей строке записано единственное целое число m (1 ≤ m ≤ 3·105) — количество раз, которое Петя перекрашивал своих солдатиков.
В следующих m строках записано по два целых числа через пробел: kj и xj (1 ≤ kj ≤ n, 1 ≤ xj ≤ 109) — порядковый номер солдатика и номер цвета, в который Петя его перекрасил (возможно, тот же самый, что и был до перекраски).
Выведите единственное число — количество перекрасок, которое сделал Петя до того, как все его солдатики впервые стали покрашены в один и тот же цвет. В частности, если они сразу же, до начала всех действий Пети, были покрашены в один и тот же цвет, выведите «0». Если же такое событие не наступало вообще никогда, даже после m-ой перекраски, выведите «-1».
3
4 3 7
4
1 5
2 7
1 7
3 3
3
3
6 2 7
3
1 1
2 7
1 6
-1
