Wookje and His Fans

Wookje has K fan clubs. N fans came to the fan meeting he holds to celebrate becoming an adult. The fans receive registration numbers 1 through N and stand in one line in that order. The fan with registration number $i$ belongs to fan club $A_i$.

With nothing else to do, Wookje decides to perform Q actions. There are two kinds of actions.

• Action 1: Wookje picks one fan and throws that fan out of the fan meeting for not being a true fan. That fan leaves the line, and the remaining fans close the gap while keeping their order.
• Action 2: Wookje picks one fan and gives one gift to that fan and to every fan of the same fan club that continues from that fan to the left and to the right without a break, as a reward for devoted support.

After finishing the Q actions Wookje got fed up, shouted "everyone worse at algorithms than me, get out", and ended the fan meeting. He wants to know how many gifts he gave to the fans. Help him.

The first line contains K and N. ($1 \le K, N \le 10^6$)

The second line contains $A_1, A_2, \dots, A_N$. ($1 \le A_i \le K$)

The third line contains Q. ($0 \le Q \le 3 \times 10^6$)

Each of the next Q lines contains integers a and b. ($1 \le a \le 2$, $1 \le b \le N$)

If a is 1, action 1 is applied to the fan with registration number b. The same fan is never thrown out twice.

If a is 2, action 2 is applied with the fan with registration number b as the center. A fan who is already out is never used as the center.

Print the total number of gifts Wookje gave to the fans after the Q actions. Wookje has infinitely many gifts, so he never fails to give one because he ran out.

In the first example the fans belong to clubs 1, 1, 2, 3, 1 in order.

At the first action 2, registration numbers 1 and 2 receive gifts. (1-1-2-3-1)

At the second action 2, registration numbers 3 and 4 are already out, so registration numbers 1, 2, and 5 receive gifts. (1-1-1)

At the last action 2, registration number 2 is out as well, so registration numbers 1 and 5 receive gifts. (1-1)