该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师得到来一个数列a，现在想要进行如下操作，如果a1>=a2，则去掉a1,a2，以a1/a2向上取整替代a1，否则以a1+a2替代a1（相当于去除前两个数字插入一个新数），问最后的数字是多少

Format

Input

第一行一个整数$n(1 \leq n \leq 10^5)$，表示数列长度

第二行n个整数$a_i(1 \leq a_i \leq 10^{13})$，表示数列元素

Output

输出最后的数字

Samples

4
1 2 3 4

5

Limitation

1s, 1024KiB for each test case.