Задача: Гравитационная сортировка

Алгоритм гравитационной сортировки позволяет упорядочить массив целых неотрицательных чисел. Для сортировки чисел используется набор стержней и бусинок. Рассмотрим алгоритм сортировки массива целых неотрицательных чисел \([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 баллов.

Ваш ответ: