AT_joigsp2025_k ういろう (Uiro)

葵は $ 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. ( $ 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 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 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 $ の制約を満たす． --- ### Sample Explanation 2 $ 1 $ 回目の遊びでは，以下のような場合が考えられる． - 最初に，黒板に $ 0 $ を書き込む． - 次に，机にカード $ 1, 2 $ をこの順に左から右へ一列に並べる． - 現在黒板に書き込まれている整数は $ 0 $ で，机に並べたカードの列の中で左から $ 1 $ 番目のカードに書かれている整数は $ 1 $ である． $ 0 $ を黒板から消し， $ 1 $ を黒板に書き込む． - 現在黒板に書き込まれている整数は $ 1 $ で，机に並べたカードの列の中で左から $ 2 $ 番目のカードに書かれている整数は $ 2 $ である． $ 1 $ を黒板から消し， $ 3 $ を黒板に書き込む． このとき， $ 1 $ 回目の遊びで葵が食べるういろうの個数は $ 0 $ 個である． $ 1 $ 回目の遊びで葵が食べるういろうの個数は $ 1 $ 個以上にならないことが示せる．したがって， $ 0 $ を出力する． この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1,2,3,4,7 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．