AT_joi2026final_a 伝説の団子食通 (Legendary Dango Eater)

ビ太郎は $ 1 $ 本の長い串団子をおやつとして購入した．この串団子は $ N $ 個の正整数 $ A_1, A_2, \cdots, A_N $ を用いて次のように表現できる．以下， $ 0 $ 以上 $ N $ 以下の整数 $ i $ に対して， $ s_i=A_1+A_2+ \cdots +A_{i} $ と書く．ただし $ s_0=0 $ であると定める． - 串団子は $ s_N $ 個の団子が上から下に $ 1 $ 列となっている形である． - それぞれの団子の味は**甘い**もしくは**辛い**のいずれかである．それぞれの団子の味について，以下のように表すことができる． - $ i $ が $ 1 \leqq i \leqq N $ を満たす奇数ならば，上から $ s_{i - 1} + 1 $ 番目から $ s_i $ 番目までの団子は甘い味である． - $ i $ が $ 1 \leqq i \leqq N $ を満たす偶数ならば，上から $ s_{i - 1} + 1 $ 番目から $ s_i $ 番目までの団子は辛い味である． ビ太郎はこの串団子を食べるにあたり， $ Q $ 通りの計画を立てた． $ j $ 番目 ( $ 1 \leqq j \leqq Q $ ) の計画は， $ 1 \leqq L_j \leqq R_j \leqq N $ を満たす整数 $ L_j $ ， $ R_j $ によって表され，上から $ s_{L_j - 1} + 1 $ 番目から $ s_{R_j} $ 番目までの団子を食べるというものである． また，ビ太郎はこの串団子を食べるにあたり，以下のように何口かに分けて食べることにした．ここで， $ K $ はビ太郎の甘さの好みを表す正整数である． - 団子は上から順に食べ進め，どの団子もちょうど $ 1 $ 回食べる． - 一口では，串上で連続する団子を好きな個数食べることができる．このとき，この一口で食べた団子について，甘い味のものの個数から辛い味のものの個数を引いた値が $ K $ 以上ならば，ビ太郎は喜ぶ． 串団子と計画の情報が与えられたとき，それぞれの計画について，ビ太郎が喜ぶ回数として考えられる最大値を求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ K $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行に出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には $ j $ 番目の計画におけるビ太郎が喜ぶ回数として考えられる最大値を出力せよ． ---

### 小課題 1. ( $ 6 $ 点) $ Q \leqq 10 $ ． 2. ( $ 5 $ 点) $ K \leqq 2 $ ． 3. ( $ 18 $ 点) $ K \leqq 10 $ ． 4. ( $ 27 $ 点) $ A_1 + A_2 + \cdots + A_N \leqq 500\,000 $ ． 5. ( $ 17 $ 点) $ N \leqq 200\,000 $ ， $ Q \leqq 200\,000 $ ． 6. ( $ 27 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 1 $ 番目の計画について，ビ太郎は上から $ 1 $ 番目から $ 12 $ 番目までの団子を食べる．ビ太郎は上から一口で $ 1 $ つの団子を食べることを繰り返すことで，ビ太郎が喜ぶ回数を $ 7 $ 回にできる． $ 8 $ 回以上喜ぶようにすることはできないため， $ 7 $ を出力する． $ 2 $ 番目の計画について，ビ太郎は上から $ 3 $ 番目から $ 9 $ 番目までの団子を食べる．ビ太郎は上から一口で $ 1 $ つの団子を食べることを繰り返すことで，ビ太郎が喜ぶ回数を $ 2 $ 回にできる． $ 3 $ 回以上喜ぶようにすることはできないため， $ 2 $ を出力する． この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 2 入力例 $ 1 $ とは $ K $ の値のみが異なる． $ 1 $ 番目の計画について，ビ太郎は以下のように団子を四口で食べることで，ビ太郎が喜ぶ回数を $ 2 $ 回にできる． - 一口目には上から $ 1 $ 番目の団子から $ 5 $ 番目までの団子を食べる．甘い味のものの個数は $ 4 $ であり，辛い味のものの個数は $ 1 $ であるため，ビ太郎は喜ぶ． - 二口目には上から $ 6 $ 番目の団子のみを食べる．甘い味のものの個数は $ 0 $ であり，辛い味のものの個数は $ 1 $ であるため，ビ太郎は喜ばない． - 三口目には上から $ 7 $ 番目の団子から $ 9 $ 番目までの団子を食べる．甘い味のものの個数は $ 0 $ であり，辛い味のものの個数は $ 3 $ であるため，ビ太郎は喜ばない． - 四口目には上から $ 10 $ 番目の団子から $ 12 $ 番目までの団子を食べる．甘い味のものの個数は $ 3 $ であり，辛い味のものの個数は $ 0 $ であるため，ビ太郎は喜ぶ． $ 3 $ 回以上喜ぶようにすることはできないため， $ 2 $ を出力する． $ 2 $ 番目の計画について，ビ太郎が $ 1 $ 回以上喜ぶように食べることはできないため， $ 0 $ を出力する． この入力例は小課題 $ 1, 3, 4, 5, 6 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1, 4, 5, 6 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 500\,000 $ ． - $ 1 \leqq Q \leqq 500\,000 $ ． - $ 1 \leqq K \leqq 10^{14} $ ． - $ 1 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq L_j \leqq R_j \leqq N $ ( $ 1 \leqq j \leqq Q $ )． - 入力される値はすべて整数である．