Adventurer on a Quest

Time limit3sMemory limit256 MB

Summary
Maintain a set of completed quest numbers under insertions and range queries asking how many integers in [L, R] are not yet completed.
Level

Medium6 of 10

Topics
Hash map, Sorting, Binary search, Implementation
Solved
No attempts yet

Problem

An adventurer is a ranked player in the online RPG World Art Yggdrasil (WAY) and enjoys completing quests every day.

WAY has one quest for every integer number from −1,000,000,000-1{,}000{,}000{,}000 to 1,000,000,0001{,}000{,}000{,}000. Completing every quest in certain ranges earns achievements.

Quests cannot always be completed in order, so the number of remaining quests has to be computed for each achievement. An addon tracks the completion record and reports how many quests in a given range are still incomplete.

Given the completion record and the requests, write a program that answers every lookup request.

Input

The first line gives NN, the number of quests completed so far. (1≤N≤1,000,000)(1 \le N \le 1{,}000{,}000)

The second line gives the NN completed quest numbers Q1,…,QNQ_1, \dots, Q_N. (−1,000,000,000≤Qi≤1,000,000,000,Qi<Qi+1)(-1{,}000{,}000{,}000 \le Q_i \le 1{,}000{,}000{,}000, Q_i < Q_{i+1})

The third line gives MM, the number of requests. (1≤M≤1,000,000)(1 \le M \le 1{,}000{,}000)

Each of the following MM lines gives one request.

  • 1 X1\ X: the quest numbered XX has been completed. Record it. (−1,000,000,000≤X≤1,000,000,000)(-1{,}000{,}000{,}000 \le X \le 1{,}000{,}000{,}000)
  • 2 L R2\ L\ R: print the number of quests numbered from LL to RR inclusive that are still incomplete. (−1,000,000,000≤L≤R≤1,000,000,000)(-1{,}000{,}000{,}000 \le L \le R \le 1{,}000{,}000{,}000)

Output

For each request of type 22, print the number of incomplete quests satisfying the condition, one per line.

Examples1

  1. Example 1

    Input
    3
1 10 20
4
2 1 20
1 5
2 1 20
2 1 1
    Expected output
    17
16
0