Задача №3896. BubbleGum
Мальчик Влад недавно побывал в Японии и привёз оттуда новую жевательную резинку. Вернувшись в университет после поездки, на первой же паре Влад раздал жвачку всем своим \((N-1)\) однокурсникам и взял одну себе. Дождавшись момента, когда лектор отвернулся к доске, на счёт “три-четыре” все \(N\) студентов дружно начали надувать пузыри. Известно, что \(i\)-й студент надувает пузырь до максимально возможного размера за время \(t_i\), после чего пузырь мгновенно лопается, и студент начинает надувать пузырь заново с той же скоростью.
Всё это время преподаватель настолько увлечён тонкостями квантового математического анализа, что не слышит ничего происходящего в аудитории. И только когда все \(N\) пузырей лопнут одновременно, преподаватель услышит шум и обернётся. И уж тогда студентам достанется, а больше всех тому, кто принёс на пару \(N\) жевательных резинок.
Определите, сколько времени студенты смогут наслаждаться надуванием пузырей, не замечаемые преподавателем.
Например, если \(N=2\), \(t_1=2\), \(t_2=3\), то будет происходить следующее:
Первый студент надувает пузырь с момента времени \(t=0\) до момента времени \(t=2\), потом пузырь лопается, и он надувает пузырь заново — с момента времени \(t=2\) до момента времени \(t=4\), а потом ещё раз — с момента времени \(t=4\) до \(t=6\).
Второй студент надувает пузырь с \(t=0\) до \(t=3\) и ещё раз с \(t=3\) до \(t=6\).
В момент \(t=6\) пузыри лопаются одновременно у обоих студентов, преподаватель оборачивается и говорит: “Всё, Влад! Ты меня достал!”.
На первой строке входного файла находится одно целое число \(N\) — количество студентов (\(1\leq N \leq 10\,000\)). Следующие \(N\) строк содержат по одному целому числу \(t_1\), \(t_2\), ..., \(t_N\). Гарантируется, что \(1\leq t_i \leq 1000\).
Выведите в выходной файл одно число — время, в течение которого студенты во главе с Владом могут наслаждаться безнаказанным надуванием пузырей.
2 2 3
6
1 1
1
2 16 1
16
3 627 182 85
9699690