A10 - Resort Hotel Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点: 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