F2. Same Sum Blocks (Hard)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis problem is given in two editions, which differ exclusively in the constraints on the number n.You are given an array of integers a[1], a[2], \dots, a[n]. A block is a sequence of contiguous (consecutive) elements a[l], a[l+1], \dots, a[r] (1 \le l \le r \le n). Thus, a block is defined by a pair of indices (l, r).Find a set of blocks (l_1, r_1), (l_2, r_2), \dots, (l_k, r_k) such that:  They do not intersect (i.e. they are disjoint). Formally, for each pair of blocks (l_i, r_i) and (l_j, r_j) where i \neq j either r_i < l_j or r_j < l_i.  For each block the sum of its elements is the same. Formally, 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].  The number of the blocks in the set is maximum. Formally, there does not exist a set of blocks (l_1', r_1'), (l_2', r_2'), \dots, (l_{k'}', r_{k'}') satisfying the above two requirements with k' > k.   The picture corresponds to the first example. Blue boxes illustrate blocks. Write a program to find such a set of blocks.InputThe first line contains integer n (1 \le n \le 1500) — the length of the given array. The second line contains the sequence of elements a[1], a[2], \dots, a[n] (-10^5 \le a_i \le 10^5).OutputIn the first line print the integer k (1 \le k \le n). The following k lines should contain blocks, one per line. In each line print a pair of indices l_i, r_i (1 \le l_i \le r_i \le n) — the bounds of the i-th block. You can print blocks in any order. If there are multiple answers, print any of them.ExamplesInput
7
4 1 2 2 1 5 3
Output
3
7 7
2 3
4 5
Input
11
-5 -4 -3 -2 -1 0 1 2 3 4 5
Output
2
3 4
1 1
Input
4
1 1 1 1
Output
4
4 4
1 1
2 2
3 3

7
4 1 2 2 1 5 3

3 7 7 2 3 4 5 
['data structures', 'greedy', '*1900']