← 返回题目列表

AtCoder · tessoku_book_j

A10. 度假酒店

中文机器翻译题面 查看原题

配点: 1000 点

問題文

在某度假酒店,1 从房间号。 N 前往房间号。 有 N 个房间。 i 房间号 A_i 这是一个私人房间。在这家酒店 D 施工工作预计将在几天内进行。 d 日期是 L_d 从房间号。 R_d 不能使用最多房间号的范围。 d=1,2,\cdots D ,d 请创建一个程序,输出当天可以使用的最大房间的人数。

制約

  • 3\leq N\leq 100000
  • 1\leq D\leq 100000
  • 1\leq A_i\leq 100
  • 2\leq L_i\leq R_i\leq N - 1
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N
D
L_1 R_1
\vdots
L_D R_D

出力

D 行。d 行中, 请输出第d 请输出当天可使用的最大房间的人数。 有


入力例 1

7
1 2 5 5 2 3 1
2
3 5
4 6

出力例 1

3
5