Marichka and cookies

Limits: 2 sec., 256 MiB

Zenyk and Marichka decided to start hiking with scouts. Hike is very important thing. It is necessary to stock up on food products and distribute their consumption over the days so that there is enough for everyone. This time, Zenyk makes sure that there are enough cookies until the last day of the hike. Zenyk knows exactly how many packs of cookies should be left each day, and he counts them every evening. If Zenyk sees that there are fewer packs left than what should be left according to his calculations, he will definitely find the person who ate too many cookies and punish him.

Marichka likes cookies so much. Today, when all the scouts leave their tents and go swim in the river, Marichka plans to quietly eat some cookies. Of course, Marichka does not want to be punished and is very afraid that Zenyk will notice the loss. Marichka looked to see how many packs of cookies are in Zenyk’s backpack. She also knows how many cookies are in each pack. Marichka can’t wait to find out how many cookies she can eat without Zenyk noticing. Zenyk will notice the disappearance of cookies from a certain pack when and only when Marichka completely empties it.

Input

The first line contain one integer \(n\) – number of packs of cookies.

The second line contain \(n\) integers \(a_i\) – number of cookies in \(i\)-th pack.

Output

In a single line, print one integer – the maximum number of cookies that Marichka can eat without Zenyk noticing it.

Constraints

20% tests:

\(1 \le n \le 1000, 0 \le a_i \le 10^4\)

60% tests:

\(1 \le n \le 10^5, 0 \le a_i \le 10^4\)

20% tests:

\(1 \le n \le 10^5, 0 \le a_i \le 10^9\)

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 7 47 74	128

Notes

Marichka can eat:

• 3 cookies from tha first pack

• 6 cookies from tha second pack

• 46 cookies from tha third pack

• 73 cookies from tha fourth pack

• \(3+6+46+73=128\) cookies in total.