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], \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$.  $\left. \begin{array}{|l|l|l|l|l|l|} \hline 4 & {1} & {2} & {2} & {1} & {5} & {3} \\ \hline \end{array} \right.$ 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 \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$).


-----Output-----

In 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.


-----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

Difficulty: introductory

Starter code:

Solutions:
n = int(input())
a = [int(x) for x in input().split()]

res = {}

for i in range(n):
  sm = 0
  for j in range(i, n):
    sm += a[j]
    if sm in res:
      res[sm].append((i, j))
    else:
      res[sm] = [(i, j)]

best = 0
bestI = -1
for key in res:
  r = -1
  cnt = 0
  for (a,b) in sorted(res[key]):
    if a > r:
      cnt += 1
      r = b
    elif b < r:
      r = b
  if cnt > best:
    best = cnt
    bestI = key

x = []
r = -1
for (a, b) in sorted(res[bestI]):
  if a > r:
    x.append(str(a+1) + " " + str(b+1))
    r = b
  elif b < r:
    r = b
    x.pop()
    x.append(str(a+1) + " " + str(b+1))
  
print(best)
print("\n".join(x))


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

rec = defaultdict(list)
for j in range(n):
    for k in range(j, n):
        rec[sum(a[j:k + 1])].append((j, k))

ans = []
for k in rec.keys():
    tmp = []
    rec[k] = sorted(rec[k], key=lambda x: x[1])
    pre = -1
    for a, b in rec[k]:
        if pre >= a:
            continue
        else:
            tmp.append((a + 1, b + 1))
            pre = b
    if len(tmp) > len(ans):
        ans = tmp

print(len(ans))
for a, b in ans:
    print(a, b)

# alpha = "abcdefghijklmnopqrstuvwxyz"
# prime = 998244353 
INF = 100_000_000
# from heapq import heappush, heappop
from collections import defaultdict
t = 1#int(input())
# from math import sqrt


for test in range(t):
    n = int(input())
    # H, n = (map(int, input().split()))
    # a = []
    # for i in range(n):
    # l = input()
    # r = input()
    a = (list((list(map(int, input().split())))))
    pre = [0 for i in range(n+1)]

    for i in range(n):
        pre[i+1] = pre[i]+a[i]
    
    Sum = defaultdict(list)

    for i in range(n):
        for j in range(i, n):
            tmp = pre[j+1]-pre[i]
            # print(i,j,tmp)
            Sum[tmp].append((i,j))

    maxVal = 0
    maxSum = -1
    for key, val in list(Sum.items()):
        val.sort()
        tmp = 1
        cur = val[0][1]
        for i in range(1,len(val)):
            if val[i][0]>cur:
                tmp+=1
                cur = val[i][1]
            elif val[i][1]<=cur:
                cur = val[i][1]
        if maxVal < tmp:
            maxVal = tmp
            maxSum = key

    print(maxVal)
    val = Sum[maxSum]
    val.sort()
    ans = []
    ans.append(val[0])
    cur = val[0][1]
    for i in range(1,len(val)):
        if val[i][0]>cur:
            ans.append(val[i])
            cur = val[i][1]
        elif val[i][1]<=cur:
            ans.pop()
            ans.append(val[i])
            cur = val[i][1]
    for i in ans:
        print(i[0]+1, i[1]+1)





n = int(input())
A = list(map(int, input().split()))
if n == 1:
    print(1)
    print(1, 1)
    return
prefA = [0]
hah = {}
for i in A:
    prefA.append(prefA[-1] + i)
for i in range(n):
    for j in range(i + 1, n + 1):
        s = prefA[j] - prefA[i]
        if s not in hah:
            hah[s] = []
        hah[s].append([i + 1, j])


def lol(a):
    return a[1], a[0]


ansq = 0
bm = []
for s in hah:
    Q = hah[s]
    cnt = 0
    Q.sort(key=lol)
    ans = []
    for i in Q:
        if i[0] > cnt:
            cnt = i[1]
            ans.append(i)
    if ansq < len(ans):
        ansq = len(ans)
        bm = ans
print(ansq)
for i in bm:
    print(*i)


n = int(input())
A = list(map(int, input().split()))
if n == 1:
    print(1)
    print(1, 1)
    return
prefA = [0]
hah = {}
for i in A:
    prefA.append(prefA[-1] + i)
for i in range(n):
    for j in range(i + 1, n + 1):
        s = prefA[j] - prefA[i]
        if s not in hah:
            hah[s] = []
        hah[s].append([i + 1, j])


def lol(a):
    return a[1], a[0]


ansq = 0
bm = []
for s in hah:
    Q = hah[s]
    cnt = 0
    Q.sort(key=lol)
    ans = []
    for i in Q:
        if i[0] > cnt:
            cnt = i[1]
            ans.append(i)
    if ansq < len(ans):
        ansq = len(ans)
        bm = ans
print(ansq)
for i in bm:
    print(i[0], i[1])


def main():
    n = int(input())
    A = list(map(int, input().split()))
    if n == 1:
        print(1)
        print(1, 1)
        return
    prefA = [0]
    hah = {}
    for i in A:
        prefA.append(prefA[-1] + i)
    for i in range(n):
        for j in range(i + 1, n + 1):
            s = prefA[j] - prefA[i]
            if s not in hah:
                hah[s] = []
            hah[s].append([i + 1, j])


    def lol(a):
        return a[1], a[0]


    ansq = 0
    bm = []
    for s in hah:
        Q = hah[s]
        cnt = 0
        Q.sort(key=lol)
        ans = []
        for i in Q:
            if i[0] > cnt:
                cnt = i[1]
                ans.append(i)
        if ansq < len(ans):
            ansq = len(ans)
            bm = ans
    print(ansq)
    for i in bm:
        print(i[0], i[1])


main()

def main():
    n = int(input())
    A = list(map(int, input().split()))
    if n == 1:
        print(1)
        print(1, 1)
        return
    prefA = [0]
    hah = {}
    for i in A:
        prefA.append(prefA[-1] + i)
    for i in range(n):
        for j in range(i + 1, n + 1):
            s = prefA[j] - prefA[i]
            if s not in hah:
                hah[s] = []
            hah[s].append([i + 1, j])


    def lol(a):
        return a[1], a[0]


    ansq = 0
    bm = []
    for s in hah:
        Q = hah[s]
        cnt = 0
        Q.sort(key=lol)
        ans = []
        for i in Q:
            if i[0] > cnt:
                cnt = i[1]
                ans.append(i)
        if ansq < len(ans):
            ansq = len(ans)
            bm = ans
    print(ansq)
    for i in bm:
        print(i[0], i[1])


main()

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import defaultdict


def find_max_non_intersecting(segments):
    n = len(segments)

    r = -1
    result = []
    for i in range(n):
        a, b = segments[i]
        if a > r:
            result.append((a, b))
            r = b

    return result


def __starting_point():
    n = int(input())
    a = list(map(int, input().split()))

    s = []
    for ai in a:
        s.append((s[-1] if s else 0) + ai)

    d = defaultdict(list)
    for j in range(n):
        for i in range(j + 1):
            d[s[j] - (s[i - 1] if i - 1 >= 0 else 0)].append((i, j))

    vals = []
    for v in list(d.values()):
        non_inters = find_max_non_intersecting(v)
        if len(non_inters) > len(vals):
            vals = non_inters

    print(len(vals))
    for l, r in vals:
        print(l + 1, r + 1)

__starting_point()

#!/usr/bin/env python3
from collections import defaultdict


def main():
    n = int(input())
    a = [int(ai) for ai in input().split()]

    pref_sums = [0] * (n + 1)
    for i, ai in enumerate(a):
        pref_sums[i + 1] = pref_sums[i] + ai

    block_sums = defaultdict(list)
    for j in range(1, n + 1):
        for i in range(1, j + 1):
            block_sums[pref_sums[j] - pref_sums[i - 1]].append((i, j))

    ans = []
    for A in list(block_sums.values()):
        res, k = [A[0]], 0
        for i in range(1, len(A)):
            if A[i][0] > A[k][1]:
                res.append(A[i])
                k = i

        if len(res) > len(ans):
            ans = res

    print(len(ans))
    print('\n'.join(['%d %d' % s for s in ans]))


def __starting_point():
    main()

__starting_point()

n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
    sm=0
    for j in range(i,n):
        sm+=a[j]
        if sm in dic:
            dic[sm].append((i,j))
        else:
            dic[sm]=[(i,j)]
ans=0
anskey=-1
for key in dic:
    cnt=0
    last=-1
    for a,b in sorted(dic[key]):
        if a>last:
            cnt+=1
            last=b
        elif b<last:
            last=b
    if cnt>ans:
        ans=cnt
        anskey=key
last=-1
tmp=[]
for a,b in sorted(dic[anskey]):
    if a>last:
        last=b
        tmp.append(str(a+1)+" "+str(b+1))
    elif b<last:
        last=b
        tmp.pop()
        tmp.append(str(a+1)+" "+str(b+1))
print(ans,'\n'.join(tmp),sep='\n')

import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

from itertools import accumulate
SUM=list(accumulate(A))
SUM.append(0)

BLIST=[[0]*n for i in range(n)]
B2=[]

for i in range(n):
    for j in range(i,n):
        BLIST[i][j]=SUM[j]-SUM[i-1]
        B2.append(SUM[j]-SUM[i-1])

B2=sorted(set(B2))
DICT={B2[i]:i for i in range(len(B2))}
USED=[-1]*len(B2)

ANS=[[] for i in range(len(B2))]

for i in range(n):
    for j in range(i+1):
        x=BLIST[j][i]

        if USED[DICT[x]]<j:
            ANS[DICT[x]].append([j+1,i+1])
            USED[DICT[x]]=i

ANS0=max(ANS,key=lambda x:len(x))
print(len(ANS0))
for ans in ANS0:
    print(*ans)
        
        


from collections import defaultdict
from itertools import accumulate

N = int(input())
H = defaultdict(lambda: [])
A = list(map(int, input().split()))
AA = [0] + list(accumulate(A))
for i in range(1, N+1):
    for j in range(i):
        H[AA[i] - AA[j]].append((i, j)) 
ctr = 0
ans = []
for L in list(H.values()):
    if ctr >= len(L):
        continue
    L.sort()
    ansc = []
    pi = -1
    for i, j in L:
        if j >= pi:
            ansc.append((j+1, i))
            pi = i
    if ctr < len(ansc):
        ans = ansc.copy()
        ctr = len(ans)
print(ctr)
for j, i in ans:
    print(j, i)


franxx = int(input())

life = input()
life = life.split()

darling = {}

oh_pay = "I love my darling"

for i in range(franxx, 0, -1):
	tmp = 0
	for j in range(i - 1, franxx):
		tmp += int(life[j])
		if (tmp in darling):
			if (darling[tmp][0] > j):
				darling[tmp] = (i - 1, 1 + darling[tmp][1])
		else:
			darling[tmp] = (i - 1, 1)
		if (oh_pay == "I love my darling" or darling[tmp][1] > darling[oh_pay][1]):
			oh_pay = tmp

print(darling[oh_pay][1])

strelizia = (franxx, 0)

for i in range(franxx, 0, -1):
	tmp = 0
	for j in range(i - 1, franxx):
		tmp += int(life[j])
		if (tmp != oh_pay):
			continue;
		if (strelizia[0] > j):
			print(i, j + 1)
			strelizia = (i - 1, 1 + strelizia[1])

from collections import defaultdict
n = int(input())
nums = list(map(int, input().split()))
freq = defaultdict(list)

for i in range(n):
	for j in range(i+1, n+1):
		freq[sum(nums[i:j])].append((i+1, j))

ans = []
for k in freq:
	l = freq[k]
	l.sort(key=lambda x: x[1])
	tmp = [l[0]]
	for i, j in l:
		if i <= tmp[-1][1]:
			continue
		tmp.append([i, j])
	
	if len(tmp) > len(ans):
		ans = tmp
print (len(ans))
for i, j in ans:
	print (i, j)

# -*- coding: utf-8 -*-
# @Time    : 2019/3/21 12:10
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : F2. Same Sum Blocks (Hard).py

from collections import defaultdict


def main():
    n = int(input())
    a = list(map(int, input().split()))

    sum_dict = defaultdict(list)
    for r in range(n):
        tmp = 0
        for l in range(r, -1, -1):
            tmp += a[l]
            sum_dict[tmp].append((l + 1, r + 1))

    ret, blocks = 0, []
    for k, v in list(sum_dict.items()):
        right, tmp = -1, 0
        curr_list = []
        for s in v:
            if s[0] > right:
                tmp += 1
                curr_list.append(s)
                right = s[1]
        if tmp > ret:
            ret = tmp
            blocks = curr_list

    print(ret)
    for s in blocks:
        print(*s)


def __starting_point():
    main()

__starting_point()

n=int(input())

a=[int(i) for i in input().split()]

pref=[0]

d={}

for x in range(len(a)):
	pref.append(pref[x]+a[x])

for r in range(n):
	for l in range(0,r+1):
		v=pref[r+1]-pref[l]

		if(v in d):
			d[v].append([l,r])
		else:
			d[v]=[[l,r]]

maxi=-2

max_set=[]

for key in d:

	start=-1

	tmp_set=[]

	ctr=0

	for e in range(len(d[key])):

		if(d[key][e][0]>start):
			tmp_set.append(d[key][e])
			start=d[key][e][1]
			ctr+=1

	if(ctr>maxi):
		maxi=ctr
		max_set=tmp_set

print(maxi)
for w in range(maxi):
	print(max_set[w][0]+1,max_set[w][1]+1)




from itertools import accumulate

n = int(input())
arr = list(map(int, input().split()))
arr_sums = [0] + list(accumulate(arr))

blocks = {}
for i in range(1, n+1):
    for j in range(i):
        total = arr_sums[i] - arr_sums[j]
        if total not in blocks:
            blocks[total] = [(j+1, i)]
        else:
            if blocks[total][-1][1] < j+1:
                blocks[total].append((j+1, i))

max_block = sorted([(i, len(x)) for i, x in list(blocks.items())], key=lambda y: (-y[1], y[0]))
print(max_block[0][1])
for item in blocks[max_block[0][0]]:
    print(item[0], item[1])



def find(v: int, s: int):
    nonlocal d, a, n
    left, r = 0, v
    if s == -5:
        print('v', v, d[s][v], d[s][:v])
    while r - left > 1:
        mid = (left + r) // 2
        if s == -5 and v == 6:
            print(d[s][v][0], d[s][mid][1])
        if d[s][v][0] > d[s][mid][1]:
            left = mid
        else:
            r = mid
    return left


n = int(input())
a = list(map(int, input().split()))
d = dict()
for i in range(n):
    s = 0
    for j in range(i, n):
        s += a[j]
        if s in d:
            d[s].append((i + 1, j + 1))
        else:
            d[s] = [(i + 1, j + 1)]
for i in list(d.keys()):
    d[i].sort(key=lambda x: x[1])

# print(d)
ar = []
for el in list(d.keys()):
    cur = []
    r = 0
    for i in d[el]:
        if i[0] > r:
            cur.append(i)
            r = i[1]
    if len(ar) < len(cur):
        ar = cur

print(len(ar))
for i in ar:
    print(*i)


# import time
def index(key, item, index):
    if key in index:
        index[key].append(item)
    else:
        index[key] = [item]

def schedule_(times, n):
    "A slower implementation."
    d = [None] * (n + 1)
    for start, end in times:
        for i in range(start + 1):
            if d[i] is None or end < d[i][1]:
                d[i] = (start, end)
    # print('d:', d)
    result = []
    next_ = d[0]
    while next_:
        result.append(next_)
        s = next_[1]
        next_ = d[s]
    return result

def schedule(times):
    # assume this is true as times.sort(key=lambda x: x[0])
    # times.sort(key=lambda x: x[1])
    index_by_b = {}
    for time in times:
        index(time[1], time, index_by_b)
    b_keys = sorted(list(index_by_b.keys()))
    result = []
    a_min = 0
    # Get interval with minimun end time whose start time >= a_min.
    for end_time in b_keys:
        start = index_by_b[end_time][-1][0]
        if start >= a_min:
            result.append((start, end_time)) 
            a_min = end_time
    return result
                
def test_schedule():
    i = [(0, 4), (2, 4), (0, 2), (0, 1), (1, 2), (2, 3), (3, 4)]
    result = schedule(i)
    print('len:', len(result))
    for ele in result:
        print(ele)

def solve(n, a_l):
    index_by_sum = {}
    # for j in range(1, n + 1):
        # sum_ = 0
        # for i in range(j - 1, -1, -1):
    for i in range(n):
        sum_ = 0
        for j in range(i + 1, n + 1):
            sum_ += a_l[j - 1]
            # print(i, j, sum_)
            if sum_ in index_by_sum:
                index_by_sum[sum_].append((i, j))
            else:
                index_by_sum[sum_] = [(i, j)]
    # print('haha')
    result = []
    for sum_, times in index_by_sum.items():
        # print('Finished sum:', sum_)
        sub_result = schedule(times)
        if len(sub_result) > len(result):
            result = sub_result
    return result

def main():
    n = int(input())
    a_l = list(map(int, input().split()))
    # n = 1500
    # a_l = range(1, n + 1)
    # tick = time.time()
    result = solve(n, a_l)
    print(len(result))
    for a, b in result:
        print(a + 1, b)
    # tock = time.time()
    # print('T:', round(tock - tick, 5))

def __starting_point():
    main()
__starting_point()

def index(key, item, index):
    if key in index:
        index[key].append(item)
    else:
        index[key] = [item]

def schedule(times):
    index_by_b = {}
    for time in times:
        index(time[1], time, index_by_b)
    b_keys = sorted(list(index_by_b.keys()))
    result = []
    a_min = 0
    # Get interval with minimun end time whose start time >= a_min.
    for end_time in b_keys:
        start = index_by_b[end_time][-1][0]
        if start >= a_min:
            result.append((start, end_time)) 
            a_min = end_time
    return result
                
def solve(n, a_l):
    index_by_sum = {}
    for i in range(n):
        sum_ = 0
        for j in range(i + 1, n + 1):
            sum_ += a_l[j - 1]
            if sum_ in index_by_sum:
                index_by_sum[sum_].append((i, j))
            else:
                index_by_sum[sum_] = [(i, j)]
    result = []
    for sum_, times in index_by_sum.items():
        sub_result = schedule(times)
        if len(sub_result) > len(result):
            result = sub_result
    return result

def main():
    n = int(input())
    a_l = list(map(int, input().split()))
    result = solve(n, a_l)
    print(len(result))
    for a, b in result:
        print(a + 1, b)

def __starting_point():
    main()
__starting_point()