Problem: This 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], ..., a[n]. A block is a sequence of contiguous (consecutive) elements a[l], a[l+1], ..., a[r] (1 ≤ l ≤ r ≤ 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), ..., (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 ≠ 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]+...+a[r_1]=a[l_2]+a[l_2+1]+...+a[r_2]= ... = a[l_k]+a[l_k+1]+...+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'), ..., (l_{k'}', r_{k'}') satisfying the above two requirements with k' > k. 

<image> The picture corresponds to the first example. Blue boxes illustrate blocks.

Write a program to find such a set of blocks.

Input

The first line contains integer n (1 ≤ n ≤ 1500) — the length of the given array. The second line contains the sequence of elements a[1], a[2], ..., a[n] (-10^5 ≤ a_i ≤ 10^5).

Output

In the first line print the integer k (1 ≤ k ≤ n). The following k lines should contain blocks, one per line. In each line print a pair of indices l_i, r_i (1 ≤ l_i ≤ r_i ≤ n) — the bounds of the i-th block. You can print blocks in any order. If there are multiple answers, print any of them.

Examples

Input


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

Solution (in JAVA):

Solution:
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class F11141 {
	static class Solver {

		ArrayList<int[]> ranges[];
		HashMap<Long, Integer> hm = new HashMap<>();

		int id(long s) {
			if (!hm.containsKey(s))
				hm.put(s, hm.size());
			return hm.get(s);
		}
		
		// max disjoint range set in ranges[r]
		int[] memo;
		int go(int r) {
			memo[N] = 0;
			int last = N;
			for(int[] a : ranges[r]) {
				while(a[0] < last) {
					memo[last - 1] = memo[last];
					last--;
				}
				memo[a[0]] = Math.max(memo[a[0]], Math.max(memo[a[0]], 1 + memo[a[1] + 1]));
				last = a[0];
			}
			while(0 < last) {
				memo[last - 1] = memo[last];
				last--;
			}
			return memo[0];
		}

		ArrayDeque<int[]> ans = new ArrayDeque<>();
		
		void go2(int r) {
			memo[N] = 0;
			int last = N;
			int minAt[] = new int[N], oo = 987654321;
			Arrays.fill(minAt, oo);
			for(int[] a : ranges[r]) {
				minAt[a[0]] = Math.min(minAt[a[0]], a[1] - a[0]);
				while(a[0] < last) {
					memo[last - 1] = memo[last];
					last--;
				}
				memo[a[0]] = Math.max(memo[a[0]], Math.max(memo[a[0]], 1 + memo[a[1] + 1]));
				last = a[0];
			}
			while(0 < last) {
				memo[last - 1] = memo[last];
				last--;
			}
			int k = 0;
			for(; k < N;) {
				if(minAt[k] == oo || memo[k] != 1 + memo[k + minAt[k] + 1]) k++;
				else {
					ans.push(new int[] {k, k + minAt[k]});
					k += minAt[k] + 1;
				}
			}
		}
		
		@SuppressWarnings("unchecked")
		Solver() {
			ranges = new ArrayList[2250001];
			for (int i = 0; i < ranges.length; i++)
				ranges[i] = new ArrayList<>();
		}

		int N, LID;
		long[] a;

		void solve(Scanner s, PrintWriter out) {
			N = s.nextInt();
			a = new long[N + 1];
			for (int i = 1; i <= N; i++)
				a[i] = s.nextLong() + a[i - 1];
			for (int i = N; i >= 1; i--)
				for (int j = i; j <= N; j++) {
					int x = id(a[j] - a[i - 1]);
					ranges[x].add(new int[] { i - 1, j - 1 });
				}
			
			int best = 0, bid = -1;
			memo = new int[N + 1];
			Arrays.sort(ranges, (a, b) -> b.size() - a.size());
			for(int i = 0; i < ranges.length; i++, LID++) {
				if(ranges[i].size() <= best) break;
				int ans = go(i);
				if(ans > best) {
					best = ans;
					bid = i;
				}
			}
			
			// backtrack on bid
			out.println(best);
			go2(bid);
						
			while(!ans.isEmpty()) {
				int[] c = ans.pop();
				out.println(++c[0] + " " + ++c[1]);
			}
			
		}

	}

	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		Solver solver = new Solver();
		solver.solve(s, out);

		out.close();

	}
}