Задача №113017. Блины
Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача.
\(N\) гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке \(i\)-го гостя лежит \(a_i\) блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из \(a_i\).
Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.
Гости хотят переложить блины таким образом, чтобы после перекладывания они съели все блины за минимальное время (которое равно наибольшему числу блинов на тарелках у гостей, включая нового гостя). Определите, за какое наименьшее время гости смогут съесть свои блины после перекладывания.
Программа получает на вход натуральное число \(N\), не превосходящее 100.000, – первоначальное количество гостей. Следующие \(N\) строк содержат натуральные числа \(a_i\) – количество блинов на тарелке \(i\)-го человека. Значения \(a_i\) даны в порядке неубывания, то есть \(a_i \le a_{i+1}\). Сумма значений всех \(a_i\) не превосходит \(2\times10^9\).
Программа должна вывести одно целое число – минимальное время, за которое все гости закончат есть свои блины после перекладывания части блинов на тарелку нового гостя.
Пояснение к примеру
За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.
4 1 3 5 6
4