сортировки

Алгоритм гравитационной сортировки позволяет упорядочить массив целых неотрицательных чисел. Для сортировки чисел используется набор стержней и бусинок. Рассмотрим алгоритм сортировки массива целых неотрицательных чисел \([a_1, a_2, ..., a_n]\). Если данные числа могут достигать значения \(n\), нужно использовать \(n\) стержней и \(a_1+a_2+...+a_n\) бусинок. Наденем по одной бусинке на самые левые \(a_1\) стержней, они представляют значение \(a_1\). Затем наденем по одной бусинке на самые левые \(a_2\) стержней, разместив их во втором ряду, над первым рядом бусинок. При этом, если \(a_2>a_1\), то некоторые бусинки второго ряда окажутся как бы висящими в воздухе, они не будут опираться на бусинки нижнего ряда. Затем на самых левых \(a_3\) стержнях в третьем ряду разместим \(a_3\) бусинок, часть из них также может не опираться ни на какие предыдущие бусинки и т.д. После того, как все бусинки будут размещены, они начинают двигаться по стержням вниз. Когда движение завершится, количество бусинок в каждом ряду будет равно значениям упорядоченного массива.

Будем считать, что все бусинки двигаются одновременно. За секунду одна бусинка сползает на один ряд вниз, если в ряду ниже пусто или находится бусинка, которая также спускается вниз. На рисунках показано начальное расположение бусинок для массива \([2, 4, 1, 5, 3]\) и состояние через 1, 2 и 3 секунды.

Для каждого стержня определите время, необходимое для того, чтобы на этом стержне все бусинки закончили движение. В данном примере на первом стержне бусинки будут неподвижны, на втором стержне они закончат движение через одну секунду, на третьем и четвёртом стержнях — через две секунды, на пятом стержне — через три секунды.

Первая строка входных данных содержит число \(n\) (\(1\le n\le 10^5\)) — количество сортируемых чисел и количество стержней (то есть максимальное значение одного числа). Следующие \(n\) строк содержат по одному числу \(a_i\) (\(0\le a_i\le n\)) — значения упорядочиваемых чисел (начальные значения числа бусинок в каждом ряду).

Для каждого из \(n\) стержней слева направо программа должна вывести одно число — количество секунд, через которое на данном стержне бусинки прекратят движение.

Решения, правильно работающие при \(n\le 10\), будут оцениваться в 30 баллов.

Решения, правильно работающие при \(n\le 2000\), будут оцениваться в 60 баллов.

Космическая станция «Орион» принимает сигналы от спутников-разведчиков. Приёмная матрица станции имеет размер 640 строк на 480 позиций. При получении каждого сигнала в журнал записываются координаты активированного элемента матрицы: номер строки и номер позиции в строке.

Элемент матрицы, который принял хотя бы один сигнал, считается активным. Элемент, который не принял ни одного сигнала, считается неактивным.

Для анализа качества связи нужно найти наибольшую непрерывную цепочку активных элементов в одной строке.

Определите наибольшую длину цепочки активных элементов, расположенных подряд в одной строке, и номер этой строки. Если таких строк несколько, укажите максимальный из их номеров.


Формат входных данных

В первой строке записано целое число N — количество принятых сигналов (1 ≤ N ≤ 10000).

В каждой из следующих N строк записаны по два числа через пробел:
- номер строки (целое число от 1 до 640)
- номер позиции в строке (целое число от 1 до 480)

Один и тот же элемент матрицы может получить несколько сигналов (координаты могут повторяться).

Формат выходных данных

Два целых числа через пробел: наибольшая длина цепочки активных элементов и номер строки, в которой она находится.