욱제와 그의 팬들

욱제에게는 팬클럽이 K개 있습니다. 욱제가 성인이 된 것을 기념해 여는 팬미팅에 팬 N명이 모였습니다. 팬은 등록번호 1번부터 N번까지를 받아 그 순서대로 한 줄로 서 있고, 등록번호 $i$번 팬은 $A_i$번 팬클럽 소속입니다.

할 일이 없던 욱제는 행동을 Q번 하기로 합니다. 행동은 두 가지입니다.

• 행동 1: 팬을 한 명 골라 진정한 팬이 아니라는 이유로 팬미팅에서 퇴출시킵니다. 퇴출된 팬은 줄에서 빠지고, 남은 팬은 순서를 유지한 채 줄을 좁혀 섭니다.
• 행동 2: 팬을 한 명 골라, 그 팬과 그 팬에서 양옆으로 끊기지 않고 이어지는 같은 팬클럽 소속 팬 모두에게 헌신적인 팬이 되어준 보상으로 선물을 하나씩 줍니다.

욱제는 Q번의 행동을 마친 뒤 너무 질린 나머지 "나보다 알고리즘 못하는 사람들 다 나가"를 시전해 팬미팅을 종료시켰습니다. 욱제는 팬미팅이 끝난 후 팬들에게 준 선물의 수를 알고 싶어 합니다. 욱제를 도와주세요.

첫째 줄에 K와 N이 주어집니다. ($1 \le K, N \le 10^6$)

둘째 줄에 $A_1, A_2, \dots, A_N$이 주어집니다. ($1 \le A_i \le K$)

셋째 줄에 Q가 주어집니다. ($0 \le Q \le 3 \times 10^6$)

이어지는 Q개의 줄에 정수 a와 b가 하나씩 주어집니다. ($1 \le a \le 2$, $1 \le b \le N$)

a가 1이면 등록번호 b번 팬을 대상으로 행동 1을 합니다. 같은 팬이 두 번 퇴출되는 일은 없습니다.

a가 2이면 등록번호 b번 팬을 기준으로 행동 2를 합니다. 이미 퇴출된 팬은 기준이 되지 않습니다.

Q번의 행동을 마친 뒤 욱제가 팬들에게 준 선물의 총 개수를 출력합니다. 욱제는 선물을 무한히 가지고 있어서 선물이 모자라 주지 못하는 경우는 없습니다.

첫 번째 예제에서 팬이 소속된 팬클럽은 차례대로 1, 1, 2, 3, 1입니다.

첫 번째 행동 2에서는 등록번호 1번과 2번이 선물을 받습니다. (1-1-2-3-1)

두 번째 행동 2에서는 등록번호 3번과 4번이 이미 퇴출되어 등록번호 1번, 2번, 5번이 선물을 받습니다. (1-1-1)

마지막 행동 2에서는 등록번호 2번도 퇴출되어 등록번호 1번과 5번이 선물을 받습니다. (1-1)