K - ういろう (Uiro) Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点： 100 点

葵は N 枚のカードを持っていて，カードには 1 から N までの番号が付けられている．各カードには 1 つの正の整数が書かれており，カード i (1 \leqq i \leqq N) に書かれた整数は A_i である．

葵はカードと黒板を用いて Q 回の遊びを行う．j 回目 (1 \leqq j \leqq Q) に行う遊びは以下のようなものである．

  • 黒板に 0 を書き込む．
  • 机にカード L_j, L_j + 1, \dots, R_j をこの順に左から右へ一列に並べる．
  • 以下の行動を R_j - L_j + 1 回行う．k 回目 (1 \leqq k \leqq R_j - L_j + 1) の行動は以下のようなものである．
    • 現在黒板に書き込まれている整数を x とし，机に並べたカードの列の中で左から k 番目のカードに書かれている整数を y とする．x を黒板から消し，x + y または x - y を黒板に書き込む．x - y を黒板に書き込んだ場合，ういろう（和菓子）を 1 個食べる．
    • ただし，0 より小さい整数を黒板に書き込むことはできない．

あなたは，それぞれの遊びにおいて葵が食べるういろうの個数としてありうる最大の値を知りたい．

カードと遊びの情報が与えられたとき，それぞれの遊びにおいて葵が食べるういろうの個数としてありうる最大の値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

標準出力に Q 行出力せよ．j 行目 (1 \leqq j \leqq Q) には，j 回目の遊びにおいて，葵が食べるういろうの個数としてありうる最大の値を出力せよ．

制約

  • 1 \leqq N \leqq 200\,000．
  • 1 \leqq A_i \leqq 100 (1 \leqq i \leqq N)．
  • 1 \leqq Q \leqq 200\,000．
  • 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q)．
  • 入力される値はすべて整数である．

小課題

  1. (7 点) N \leqq 20，Q \leqq 20．
  2. (11 点) N \leqq 300，Q \leqq 20．
  3. (15 点) N \leqq 5\,000，Q \leqq 20．
  4. (24 点) Q \leqq 20．
  5. (21 点) A_i \leqq 2 (1 \leqq i \leqq N)．
  6. (14 点) A_i \leqq 20 (1 \leqq i \leqq N)．
  7. (8 点) 追加の制約はない．

入力例 1

5
3 4 7 2 8
2
1 3
4 4

出力例 1

1
0

1 回目の遊びでは，以下のような場合が考えられる．

  • 最初に，黒板に 0 を書き込む．
  • 次に，机にカード 1, 2, 3 をこの順に左から右へ一列に並べる．
  • 現在黒板に書き込まれている整数は 0 で，机に並べたカードの列の中で左から 1 番目のカードに書かれている整数は 3 である．0 を黒板から消し，3 を黒板に書き込む．
  • 現在黒板に書き込まれている整数は 3 で，机に並べたカードの列の中で左から 2 番目のカードに書かれている整数は 4 である．3 を黒板から消し，7 を黒板に書き込む．
  • 現在黒板に書き込まれている整数は 7 で，机に並べたカードの列の中で左から 3 番目のカードに書かれている整数は 7 である．7 を黒板から消し，0 を黒板に書き込む．ういろうを 1 個食べる．

このとき，1 回目の遊びで葵が食べるういろうの個数は 1 個である．1 回目の遊びで葵が食べるういろうの個数は 2 個以上にならないことが示せる．したがって，1 を出力する．

2 回目の遊びでは，以下のような場合が考えられる．

  • 最初に，黒板に 0 を書き込む．
  • 次に，机にカード 4 を並べる．
  • 現在黒板に書き込まれている整数は 0 で，机に並べたカードの列の中で左から 1 番目のカードに書かれている整数は 2 である．0 を黒板から消し，2 を黒板に書き込む．

このとき，2 回目の遊びで葵が食べるういろうの個数は 0 個である．2 回目の遊びで葵が食べるういろうの個数は 1 個以上にならないことが示せる．したがって，0 を出力する．

この入力例は小課題 1,2,3,4,6,7 の制約を満たす．

入力例 2

14
1 2 2 1 2 1 1 2 1 2 2 1 1 1
5
1 2
1 14
5 11
3 12
4 7

出力例 2

0
8
4
6
2

1 回目の遊びでは，以下のような場合が考えられる．

  • 最初に，黒板に 0 を書き込む．
  • 次に，机にカード 1, 2 をこの順に左から右へ一列に並べる．
  • 現在黒板に書き込まれている整数は 0 で，机に並べたカードの列の中で左から 1 番目のカードに書かれている整数は 1 である．0 を黒板から消し，1 を黒板に書き込む．
  • 現在黒板に書き込まれている整数は 1 で，机に並べたカードの列の中で左から 2 番目のカードに書かれている整数は 2 である．1 を黒板から消し，3 を黒板に書き込む．

このとき，1 回目の遊びで葵が食べるういろうの個数は 0 個である．1 回目の遊びで葵が食べるういろうの個数は 1 個以上にならないことが示せる．したがって，0 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 3

8
16 23 45 76 43 97 12 43
7
1 8
3 7
2 7
4 5
5 8
2 6
3 5

出力例 3

3
2
2
1
2
2
1

この入力例は小課題 1,2,3,4,7 の制約を満たす．