Hai con trỏ

Cho một mảng \(A\) gồm \(N\) số nguyên dương và một số nguyên \(S\). Hãy kiểm tra xem có tồn tại một mảng con liên tiếp nào của \(A\) có tổng đúng bằng \(S\) hay không. Nếu có, hãy in ra vị trí bắt đầu và kết thúc của mảng con đó (chỉ số tính từ \(1\)). Nếu có nhiều mảng con thỏa mãn, in ra mảng con có vị trí bắt đầu nhỏ nhất. Nếu không tồn tại, in ra \(-1\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(S\) (\(1 \le N \le 10^5, 1 \le S \le 10^{14}\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Output

• In ra hai số nguyên là chỉ số bắt đầu và kết thúc của mảng con. Nếu không tìm thấy, in ra \(-1\).

Example

6 12
1 3 2 5 2 1

2 5

Có \(N\) người cần di chuyển, người thứ \(i\) có khối lượng là \(W_i\). Bạn cần thuê xe đạp đôi để chở tất cả mọi người. Biết rằng mỗi chiếc xe đạp chỉ có thể chở tối đa 2 người và tổng khối lượng của những người trên xe không được vượt quá mức tải trọng cho phép là \(C\). Hãy tìm số lượng xe đạp ít nhất cần thiết để chở tất cả \(N\) người.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(C\) (\(1 \le N \le 10^5, 1 \le C \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên \(W_1, W_2, \dots, W_N\) (\(1 \le W_i \le C\)).

Output

• In ra một số nguyên duy nhất là số lượng xe đạp tối thiểu cần dùng.

Example

4 3
3 2 2 1

3

Tom đang dạo bước trên bãi biển và nhặt được một chuỗi \(N\) viên sỏi nhiều màu sắc được xếp thành một hàng ngang. Mỗi màu sắc của viên sỏi được đại diện bởi một số nguyên dương. Tom muốn cắt ra một đoạn sỏi liên tiếp để xâu thành một chiếc vòng cổ. Là một người theo đuổi sự hoàn hảo, Tom yêu cầu chiếc vòng cổ của mình không được có bất kỳ hai viên sỏi nào cùng màu (mỗi giá trị chỉ được xuất hiện tối đa một lần).

Hãy đếm xem có tổng cộng bao nhiêu cách cắt ra một đoạn sỏi liên tiếp (có độ dài lớn hơn \(0\)) thỏa mãn điều kiện khắt khe này.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) thể hiện màu sắc của các viên sỏi.

Output

• In ra một số nguyên duy nhất là tổng số cách chọn đoạn sỏi thỏa mãn. (Lưu ý: Đáp án có thể rất lớn, hãy sử dụng kiểu dữ liệu số nguyên 64-bit như long long trong C++).

Example

3
3 2 3

5

Đức Cống đang trong quá trình chiêu mộ nhân tài để thành lập studio phát triển game của riêng mình. Có \(N\) lập trình viên đến ứng tuyển, người thứ \(i\) có điểm kỹ năng là \(A_i\). Để chuẩn bị cho một dự án lớn, Đức cần lập ra đúng hai đội làm việc độc lập.

Để đảm bảo tinh thần teamwork và không ai bị "khớp" khi làm việc chung, Đức đưa ra một quy tắc khắt khe: Trong cùng một đội, mức chênh lệch kỹ năng giữa người giỏi nhất và người yếu nhất không được vượt quá \(K\). Một người chỉ có thể tham gia tối đa một đội, và một đội có thể có số lượng thành viên tùy ý (thậm chí là \(0\) người).

Vì muốn studio có quy mô lớn nhất có thể, hãy giúp Đức tính xem có thể tuyển tối đa bao nhiêu nhân viên vào hai đội này.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 2 \cdot 10^5, 0 \le K \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)) thể hiện điểm kỹ năng của các lập trình viên.

Output

• In ra một số nguyên duy nhất là tổng số nhân viên tối đa có thể được chọn vào cả hai đội.

Example

7 2
1 5 3 2 8 7 8

6

Tiếp tục dự án game chiến thuật của mình, Đức Cống đang thiết kế hệ thống sinh bản đồ tự động. Bản đồ được biểu diễn dưới dạng một lưới tọa độ hình chữ nhật gồm \(N\) dòng và \(M\) cột. Mỗi ô trên lưới mang một trong hai giá trị: \(0\) (tương ứng với đất trống) hoặc \(1\) (tương ứng với hang ổ quái vật).

Để tạo khu vực "Tân thủ thôn" (vùng an toàn cho người chơi mới), Đức cần khoanh vùng một ma trận con (một hình chữ nhật gồm các ô liên tiếp) có diện tích lớn nhất có thể. Tuy nhiên, để người chơi có chút thử thách nhẹ nhàng nhưng không bị choáng ngợp, khu vực này được phép chứa tối đa \(K\) hang ổ quái vật.

Hãy lập trình giúp Đức tìm diện tích lớn nhất của "Tân thủ thôn" thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, M\) và \(K\) (\(1 \le N, M \le 500, 0 \le K \le N \cdot M\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên (chỉ gồm \(0\) và \(1\)) mô tả bản đồ.

Output

• In ra một số nguyên duy nhất là diện tích lớn nhất của ma trận con tìm được.

Example

3 3 1
0 0 0
1 0 1
0 0 0

6

Subtask \(1(50\%)\): Ma trận chỉ có một hàng hoặc một cột
Subtask \(2(50\%)\): Không có ràng buộc gì thêm

Mỗi dãy con được gọi là dãy con liên tiếp nếu dãy con đó có dạng \(a_i, a_{i+1}, a_{i+2}, \dots, a_j\) với \(1 \leq i \leq j \leq n\), là dãy con của dãy \(a\) gồm \(n\) phần tử cho trước.

Cho một dãy gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) và hai số nguyên dương \(p, q\). Người ta muốn đếm số các dãy con liên tiếp của dãy số đã cho có tổng các số lớn hơn hoặc bằng \(p\) và nhỏ hơn hoặc bằng \(q\).

Yêu cầu

Hãy lập trình đếm số các dãy con liên tiếp thỏa mãn điều kiện bài toán.

Input

• Dòng đầu ghi ba số nguyên \(n, p, q\) (\(2 \leq n \leq 10^5; 1 \leq p \leq q \leq 10^9\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^5, i = 1, 2, \dots, n\)).

Output

• Một số nguyên duy nhất là số các dãy con liên tiếp thỏa mãn có tổng các số nằm trong đoạn \([p, q]\).

Example

4 3 6
1 2 3 4

5