A - 伝説の団子食通 (Legendary Dango Eater) Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

Bitaro bought a long skewer of dumplings as a snack. This skewer can be represented by N positive integers A_1, A_2, \cdots, A_N as follows. For each integer i with 0 \leq i \leq N, let s_i = A_1 + A_2 + \cdots + A_i. In particular, we define s_0 = 0.

  • The skewer consists of s_N dumplings arranged in a single column from top to bottom.
  • Each dumpling is either sweet or spicy. The taste of each dumpling can be described as follows.
    • If i is an odd integer satisfying 1 \leq i \leq N, then the dumplings from the (s_{i-1} + 1)-th to the s_i-th from the top are sweet.
    • If i is an even integer satisfying 1 \leq i \leq N, then the dumplings from the (s_{i-1} + 1)-th to the s_i-th from the top are spicy.

When eating this skewer of dumplings, Bitaro made Q possible plans. The j-th plan (1 \leq j \leq Q) is represented by integers L_j and R_j satisfying 1 \leq L_j \leq R_j \leq N, and in this plan he eats the dumplings from the (s_{L_j-1}+1)-th from the top through the s_{R_j}-th from the top.

Also, when eating this skewer, Bitaro decided to divide it into several bites in the following manner. Here, K is a positive integer representing Bitaro's preference for sweetness.

  • He eats the dumplings from top to bottom, and each dumpling is eaten exactly once.
  • In one bite, he may eat any positive number of consecutive dumplings on the skewer. If, among the dumplings eaten in that bite, the number of sweet dumplings minus the number of spicy dumplings is at least K, then Bitaro is pleased.

Given the information about the skewer of dumplings and the plans, write a program that, for each plan, computes the maximum possible number of times Bitaro can be pleased.

Input

Read the following data from the standard input.

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

Output

Write Q lines to the standard output. In the j-th line (1 \leq j \leq Q), output the maximum number of times Bitaro can be pleased in the j-th plan.

Constraints

  • 1 \leq N \leq 500\,000.
  • 1 \leq Q \leq 500\,000.
  • 1 \leq K \leq 10^{14}.
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N).
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q).
  • Given values are all integers.

Subtasks

  1. (6 points) Q \leq 10.
  2. (5 points) K \leq 2.
  3. (18 points) K \leq 10.
  4. (27 points) A_1 + A_2 + \cdots + A_N \leq 500\,000．
  5. (17 points) N \leq 200\,000, Q \leq 200\,000．
  6. (27 points) No additional constraints.

Sample Input 1

5 2 1
2 1 2 4 3
1 5
2 4

Sample Output 1

7
2

For the first plan, Bitaro eats the dumplings from the first through the 12th from the top. By repeatedly eating exactly one dumpling per bite from the top, Bitaro can be pleased 7 times. Since it is impossible to make him pleased 8 times or more, you should output 7.

For the second plan, Bitaro eats the dumplings from the third through the 9th from the top. By repeatedly eating exactly one dumpling per bite from the top, Bitaro can be pleased 2 times. Since it is impossible to make him pleased 3 times or more, you should output 2.

This sample input satisfies the constraints of all subtasks.

Sample Input 2

5 2 3
2 1 2 4 3
1 5
2 4

Sample Output 2

2
0

This differs from Sample Input 1 only in the value of K.

For the first plan, Bitaro can be pleased 2 times by eating the dumplings in the following four bites.

  • In the first bite, he eats the first through the 5th dumplings from the top. Since the number of sweet dumplings is 4 and the number of spicy dumplings is 1, Bitaro is pleased.
  • In the second bite, he eats only the 6th dumpling from the top. Since the number of sweet dumplings is 0 and the number of spicy dumplings is 1, Bitaro is not pleased.
  • In the third bite, he eats the 7th through the 9th dumplings from the top. Since the number of sweet dumplings is 0 and the number of spicy dumplings is 3, Bitaro is not pleased.
  • In the fourth bite, he eats the 10th through the 12th dumplings from the top. Since the number of sweet dumplings is 3 and the number of spicy dumplings is 0, Bitaro is pleased.

Since it is impossible to make him pleased 3 times or more, you should output 2.

For the second plan, it is impossible for Bitaro to eat the dumplings in such a way that he is pleased at least once, so you should output 0.

This sample input satisfies the constraints of subtasks 1, 3,4,5,6.

Sample Input 3

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

Sample Output 3

3
2
1
1

This sample input satisfies the constraints of subtasks 1,4,5,6.

配点： 100 点

問題文

ビ太郎は 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 \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)．
  • 入力される値はすべて整数である．

小課題

  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 点) 追加の制約はない．

入力例 1

5 2 1
2 1 2 4 3
1 5
2 4

出力例 1

7
2

1 番目の計画について，ビ太郎は上から 1 番目から 12 番目までの団子を食べる．ビ太郎は上から一口で 1 つの団子を食べることを繰り返すことで，ビ太郎が喜ぶ回数を 7 回にできる．8 回以上喜ぶようにすることはできないため，7 を出力する．

2 番目の計画について，ビ太郎は上から 3 番目から 9 番目までの団子を食べる．ビ太郎は上から一口で 1 つの団子を食べることを繰り返すことで，ビ太郎が喜ぶ回数を 2 回にできる．3 回以上喜ぶようにすることはできないため，2 を出力する．

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

入力例 2

5 2 3
2 1 2 4 3
1 5
2 4

出力例 2

2
0

入力例 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 の制約を満たす．

入力例 3

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

出力例 3

3
2
1
1

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