Các khối cùng tổng (bản khó)

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$. Một khối (block) là một dãy con gồm các phần tử liên tiếp $a_l,a_{l+1},\dots ,a_r$ (với $1\le l\le r\le n$), được xác định bởi cặp chỉ số $(l,r)$.

Hãy tìm một tập các khối $(l_1,r_1),(l_2,r_2),\dots ,(l_k,r_k)$ thoả mãn:

• Các khối đôi một rời nhau (không giao nhau): với mọi cặp khối $i\ne j$, hoặc $r_i<l_j$, hoặc $r_j<l_i$.
• Tổng các phần tử trong mỗi khối bằng nhau: $$a_{l_1}+\cdots +a_{r_1}=a_{l_2}+\cdots +a_{r_2}=\cdots =a_{l_k}+\cdots +a_{r_k}.$$
• Số khối $k$ lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: độ dài của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Dòng đầu in số nguyên $k$: số khối trong tập tìm được.
• Trong $k$ dòng tiếp theo, mỗi dòng in hai số nguyên $l_i,r_i$ mô tả một khối.

Có thể in các khối theo thứ tự bất kỳ. Nếu có nhiều đáp án cùng đạt $k$ lớn nhất, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le n\le 1500$
• $-{10}^5\le a_i\le {10}^5$

Ví dụ