시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 128 MB 262 87 31 28.440%

문제

욱제에게는 K개의 팬클럽이 있습니다. 욱제가 성인이 된 것을 기념하여 개최하는 욱제의 팬미팅에 N명의 팬이 모였습니다. N명의 팬들은 각각 순서대로 A1, A2, ..., AN 번 팬클럽에 소속되어 있으며, 등록번호 1, 2, ..., N을 가집니다. 팬들은 1, 2, ..., N번 순서로 서 있습니다.

할 일이 없었던 욱제는 Q번 어떠한 행동을 하기로 합니다. 행동에는 두가지 종류가 있습니다 :

  • 행동 1 : 욱제는 팬을 한명 골라 진정한 팬이 아니라는 이유로 팬미팅에서 퇴출시킵니다.
  • 행동 2 : 욱제는 팬을 한명 골라 그 팬을 포함해 양 옆으로 연속적으로 같은 팬클럽인 사람들에게 헌신적인 팬이 되어준 보상으로써 선물을 줍니다.

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

입력

첫 번째 줄에 K와 N이 입력됩니다. (1 ≤ K, N ≤ 106)

두 번째 줄에 A1, A2, ..., AN이 입력됩니다. (1 ≤ Ai ≤ K)

세 번째 줄에 Q가 입력됩니다. (0 ≤ Q ≤ 3 × 106)

Q개의 줄 동안 숫자 a와 b가 입력됩니다. (1 ≤ a ≤ 2, 1 ≤ b ≤ N)

a가 1일 경우엔 등록번호 b번 사람을 대상으로 행동 1을 시행하며. 이는 같은 팬에게 중복으로 발생하지 않음이 보장됩니다.

a가 2일 경우엔 등록번호 b번 사람을 기준으로 행동 2를 시행합니다. 퇴출된 사람은 대상이 되지 않습니다.

출력

Q번의 행동을 시행한 후 욱제가 팬들에게 준 총 선물의 수를 출력합니다. 욱제는 선물을 무한히 많이 가지고 있기 때문에, 선물이 부족해 선물을 줄 수 없는 경우는 없습니다.

예제 입력 1

10 5
1 1 2 3 1
6
2 2
1 3
1 4
2 5
1 2
2 5

예제 출력 1

7

힌트

첫 번째 행동 2에서 욱제는 등록번호 1, 2번에게 선물을 줍니다. ( 1-1-2-3-1 )

두 번째 행동 2에서 욱제는 등록번호 1, 2, 5번에게 선물을 줍니다. ( 1-1-1 )

마지막 행동 2에서 욱제는 등록번호 1, 5번에게 선물을 줍니다. ( 1-1 )

출처