Эта задача дана в двух редакциях, которые различаются исключительно ограничением на число \(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].\(\)
- Количество блоков в наборе максимально возможное. Формально, не существует такого набора блоков \((l_1', r_1'), (l_2', r_2'), \dots, (l_{k'}', r_{k'}')\), который удовлетворяет паре условий выше и \(k' > k\).
Картинка соответствует первому примеру. Синие прямоугольники иллюстрируют блоки. Напишите программу, которая выводит искомый набор блоков.
Выходные данные
В первую строку выведите \(k\) (\(1 \le k \le n\)). Следующие \(k\) строк должны содержать описания блоков, по одному в строке. В каждую из этих строк выведите пару индексов \(l_i, r_i\) (\(1 \le l_i \le r_i \le n\)) — границы \(i\)-го блока. Вы можете выводить блоки в любом порядке. Если ответов несколько, выведите любой из них.