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:
//package sept;

import java.io.*;
import java.util.*;


public class TimePass implements Runnable {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    //boolean debug=false;
    boolean debug=true;
    static long mod=998244353;
    static long mod2=1000000007;
    
    void solve() throws IOException
    {
        int n=ni();
        int[] a=na(n);
        long[] sum=new long[n];
        sum[0]=a[0];
        for(int i=1;i<n;i++)sum[i]=sum[i-1]+a[i];
        HashMap<Long,ArrayList<Pair>> map=new HashMap<>();
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                long curr=sum[j]-(i>0?sum[i-1]:0);
                if(map.containsKey(curr))
                {
                    map.get(curr).add(new Pair(i+1,j+1));
                }
                else
                {
                    ArrayList<Pair> list=new ArrayList<>();
                    list.add(new Pair(i+1,j+1));
                    map.put(curr,list);
                }
            }
        }
        int max=0;
        long maxSum=0;
        for(long key:map.keySet())
        {
            ArrayList<Pair> list=map.get(key);
            list.sort(new Comparator<Pair>(){
                public int compare(Pair p1,Pair p2)
                {
                    return p1.b-p2.b;
                }
            });
            int prevl=0;
            int cnt=0;
            for(Pair pr:list)
            {
                if(pr.a>prevl)
                {
                    cnt++;
                    prevl=pr.b;
                }
            }
            if(max<cnt)
            {
                max=cnt;
                maxSum=key;
            }
        }
        int prevl=0;
        ArrayList<Pair> list=map.get(maxSum);
        ArrayList<Pair> ans=new ArrayList<>();
        for(Pair pr:list)
        {
            if(pr.a>prevl)
            {
                //cnt++;
                ans.add(pr);
                //out.println(pr.a+" "+pr.b);
                prevl=pr.b;
            }
        }
        out.println(ans.size());
        for(Pair pr:ans)
        {
            out.println(pr.a+" "+pr.b);
        }
    }
    
    static long fnc(int a,int b)
    {
        return a+(long)1000000007*b;
    }
    
    static Pair[][] packU(int n,int[] from,Pair[] to)
    {
        Pair[][] g=new Pair[n][];
        int[] p=new int[n];
        for(int f:from)
        {
            p[f]++;
        }
        int m=from.length;
        for(int i=0;i<n;i++)
        {
            g[i]=new Pair[p[i]];
        }
        for(int i=0;i<m;i++)
        {
            g[from[i]][--p[from[i]]]=to[i];
        }
        return g;
    }

    static int[][] packD(int n,int[] from,int[] to)
    {
        int[][] g=new int[n][];
        int[] p=new int[n];
        for(int f:from)
        {
            p[f]++;
        }
        int m=from.length;
        for(int i=0;i<n;i++)
        {
            g[i]=new int[p[i]];
        }
        for(int i=0;i<m;i++)
        {
            g[from[i]][--p[from[i]]]=to[i];
        }
        return g;
    }
        
    static class Pair
    {
        int a,b,c;
        public Pair(int a,int b
        //,int c
        )
        {
            this.a=a;
            this.b=b;
            //this.c=c;
        }
    }
    
    static long lcm(int a,int b)
    {
        long val=a;
        val*=b;
        return (val/gcd(a,b));
    }
    
    static long gcd(long a,long b)
    {
        if(a==0)return b;
        return gcd(b%a,a);
    }
    
    static int pow(int a, int b, int p)
    {
        long ans = 1, base = a;
        while (b!=0)
        {
            if ((b & 1)!=0)
            {
                ans *= base;
                ans%= p;
            }
            base *= base;
            base%= p;
            b >>= 1;
        }
        return (int)ans;
    }

    static int inv(int x, int p)
    {
        return pow(x, p - 2, p);
    }
    
    public static long[] radixSort(long[] f){ return radixSort(f, f.length); }
    public static long[] radixSort(long[] f, int n)
    {
        long[] to = new long[n];
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(int)(f[i]&0xffff)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[(int)(f[i]&0xffff)]++] = f[i];
            long[] d = f; f = to;to = d;
        }
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>16&0xffff)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>16&0xffff)]++] = f[i];
            long[] d = f; f = to;to = d;
        }
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>32&0xffff)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>32&0xffff)]++] = f[i];
            long[] d = f; f = to;to = d;
        }
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>48&0xffff)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>48&0xffff)]++] = f[i];
            long[] d = f; f = to;to = d;
        }
        return f;
    }

    
    public void run()
    {
        if(debug)oj=true;
        is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        try {
            solve();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        out.flush();
        tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception {new Thread(null,new TimePass(),"Main",1<<26).start();}
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}