Задача C. Плотные и целые

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Последовательность целых чисел b1, b2, …, bK назовём плотной, если после сортировки по возрастанию она превратится в последовательность x, x + 1, …, x + K − 1 для некоторого целого x. Например, последовательности 1, 2 и 7, 6, 8, 5 являются плотными, а последовательности 1, 1, 2 и 1, 5, 2, 3 — нет.

Дана последовательность из N целых чисел a1, …, aN. Требуется определить такие два индекса 1 ≤ i ≤ j ≤ N, что:

  1. подпоследовательность ai, ai + 1, …, aj является плотной;
  2. длина подпоследовательности j − i + 1 является максимально возможной;
  3. индекс i — наименьший среди всех подпоследовательностей, удовлетворяющих предыдущим условиям;

Рекомендуется рассмотреть частичные решения

  1. 1 ≤ N ≤ 500
  2. 1 ≤ ai ≤ 106

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a1… aN.

Формат выходного файла

Выходной файл должен содержать два целых числа — индексы i и j.

Ограничения

1 ≤ N ≤ 10000; 1 ≤ ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
3 3
1 1
2
10
1 1 2 2 5 3 4 6 2 4
4 8

0.042s 0.007s 15