Bitaro mua một xiên dango dài để ăn nhẹ. Các viên dango được xếp thành một cột từ trên xuống dưới và chia thành các khối liên tiếp. Có \(N\) số nguyên dương \(A_1,A_2,\ldots,A_N\); khối \(i\) gồm \(A_i\) viên dango. Khối lẻ có vị ngọt, khối chẵn có vị cay. Đặt \(s_0=0\) và \(s_i=A_1+\cdots+A_i\), nên khối \(i\) chiếm các vị trí từ \(s_{i-1}+1\) đến \(s_i\) tính từ trên xuống.

Bitaro có \(Q\) kế hoạch. Kế hoạch \(j\) cho bởi \(L_j,R_j\), và Bitaro chỉ ăn các viên từ vị trí \(s_{L_j-1}+1\) đến \(s_{R_j}\).

Trong một kế hoạch, Bitaro ăn từ trên xuống dưới trong vùng đã chọn, mỗi viên đúng một lần, chia tùy ý thành các miếng liên tiếp không rỗng. Một miếng làm Bitaro vui nếu số viên ngọt trừ số viên cay trong miếng đó không nhỏ hơn \(K\). Với mỗi kế hoạch, hãy tìm số miếng làm Bitaro vui lớn nhất có thể.

Dữ liệu vào

Dòng đầu gồm \(N,Q,K\). Dòng thứ hai gồm \(A_1,A_2,\ldots,A_N\). \(Q\) dòng tiếp theo, dòng \(j\) gồm \(L_j,R_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(j\) là số lần Bitaro có thể vui nhiều nhất trong kế hoạch \(j\).

Ràng buộc

• \(1\le N,Q\le500000\).
• \(1\le K\le10^{14}\).
• \(1\le A_i\le10^9\).
• \(1\le L_j\le R_j\le N\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(Q\le10\).
2. \(5\) điểm: \(K\le2\).
3. \(18\) điểm: \(K\le10\).
4. \(27\) điểm: \(A_1+\cdots+A_N\le500000\).
5. \(17\) điểm: \(N,Q\le200000\).
6. \(27\) điểm: không có ràng buộc thêm.

Ví dụ

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

7
2

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

2
0

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

3
2
1
1

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 1, bài Legendary Dango Eater, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.