CF1141F2 Same Sum Blocks (Hard)

本题与 CF1141F1 的唯一区别在于 $ n $ 的范围。 给定一个整数数组 $ a_1, a_2, \dots, a_n $。定义区块指一段连续的元素 $ a_l, a_{l + 1}, \dots, a_r $（$ 1 \le l \le r \le n $）。因此，一个区块由一对下标 $(l, r)$ 定义。 请找出一组区块 $(l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)$，使得： - 这些区块互不相交（即两两不重叠）。形式化地，对于任意两个区块 $(l_i, r_i)$ 和 $(l_j, r_j)$，若 $i \neq j$，则要么 $r_i < l_j$，要么 $r_j < l_i$。 - 每个区块内元素的和都相等。形式化地，有 $$ a[l_{1}] + a[l_{1} + 1] + \dots + a[r_{1}] = a[l_{2}] + a[l_{2} + 1] + \dots + a[r_{2}] = \dots = a[l_{k}] + a[l_{k} + 1] + \dots + a[r_{k}] $$ - 区块的数量 $k$ 最大。形式化地，不存在另一组满足上述两个条件的区块集合 $(l_1', r_1'), (l_2', r_2'), \dots, (l_{k'}', r_{k'}')$，使得 $k' > k$。 请编写程序，找出这样一组区块。

第一行包含一个整数 $ n $（$ 1 \le n \le 1500 $），表示数组的长度。 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ -10^5 \le a_i \le 10^5 $）。

第一行输出一个整数 $ k $（$ 1 \le k \le n $）。 接下来的 $ k $ 行，每行输出一对下标 $ l_i, r_i $（$ 1 \le l_i \le r_i \le n $），表示第 $i$ 个区块的左右端点。区块可以按任意顺序输出。如果有多组答案，输出任意一组均可。

 上图对应第一个样例，蓝色框表示区块。