401517: GYM100488 D Toy Soldiers

Petya loves toy soldiers very much. He has n soldiers, and i-th soldier is painted the a_i-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.

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

The second line contains n integers a₁, ..., a_n (1 ≤ a_i ≤ 10⁹) separated by spaces — the initial colors the soldiers were painted.

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

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

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».

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