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

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

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

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

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