15816번 - 퀘스트 중인 모험가

문제

모험가 x|최강영훈|x 은 온라인 RPG 게임 월드 아트 위그드라실(WAY)에서 활동중인 랭커이다.

x|최강영훈|x 은 매일 WAY의 퀘스트를 달성하는것에 재미를 느끼고 있다.

WAY에는 -10억부터 10억까지의 모든 정수 번호에 대해 퀘스트가 하나씩 부여되어 있다. 또한 특정 범위의 퀘스트를 모두 달성하면 업적을 받을 수 있다.

x|최강영훈|x 은 퀘스트를 달성하는 김에 업적도 얻고 싶었다. 하지만 WAY에는 항상 퀘스트를 순서대로 달성할 수 없는 경우가 존재해서 업적마다 몇 개의 퀘스트를 더 달성해야하는지 매번 계산해야 하는 불편함이 존재했다.

이를 안타깝게 여긴 모험가 사투-는 특정 범위의 퀘스트 중 모험가가 달성하지 못한 퀘스트의 개수를 출력하는 애드온을 개발하기로 했다.

물론 언제나 그렇듯, 구현은 당신이 해야 한다.

입력

첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q₁ ... Q_N 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q[i] < Q[i+1])

셋째 줄에 애드온 요청의 개수 M이 주어진다. (1 ≤ M ≤ 1,000,000)

넷째 줄부터 M개의 줄에 걸쳐서 애드온에 요청할 명령이 주어진다.

1. 1 X: 퀘스트 번호 X를 달성했다. 애드온에 이를 반영해야 한다. (−1,000,000,000 ≤ X ≤ 1,000,000,000)
2. 2 L R: 퀘스트 번호 L 이상 R 이하인 퀘스트 중, 모험가가 달성하지 못한 퀘스트의 개수를 출력한다. (−1,000,000,000 ≤ L ≤ R ≤ 1,000,000,000)

출력

애드온 기능2에 해당하는 출력을 요청당 한 줄씩 출력한다.

제한

힌트