D. Toy Soldiers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Petya loves toy soldiers very much. He has n soldiers, and i-th soldier is painted the ai-th color.

Petya constantly doesn't like how his soldiers are colored so he takes one of them and repaints it. He does that m times, and Vova, watching on it, becomes interested when all the soldiers have the same color for the first time. Help Vova to answer his question.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of soldiers Petya has.

The second line contains n integers a1, ..., an (1 ≤ ai ≤ 109) separated by spaces — the initial colors the soldiers were painted.

The third line contains a single integer m (1 ≤ m ≤ 3·105) — the number of times Petya has repainted his soldiers.

The next m lines contains two integers each, separated by a space: kj and xj (1 ≤ kj ≤ n, 1 ≤ xj ≤ 109) — the number of soldier and the number of color it has been repainted (possibly the same as before the repaintment).

Output

Output a single integer — the number of repaintments Petya has made before all his soldiers have the same color for the first time. In particular, if all soldiers had the same color before all Petya's actions, output «0». If such an event has never taken place at all, even after m-th repaintment, output «-1».

Examples
Input
3
4 3 7
4
1 5
2 7
1 7
3 3
Output
3
Input
3
6 2 7
3
1 1
2 7
1 6
Output
-1