4. Triangle Spiral
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two points on the plane: $$$A$$$ and $$$B_0$$$. The length of segment $$$AB_0$$$ is 1.

From point $$$B_0$$$, a segment $$$B_0B_1$$$ of length $$$c_1$$$ is drawn perpendicular to segment $$$AB_0$$$ counter-clockwise. Similarly, from each point $$$B_i$$$, a segment $$$B_{i-1}B_i$$$ of length $$$c_i$$$ is drawn perpendicular to segment $$$AB_{i-1}$$$ counter-clockwise, $$$i = 1..N$$$. There are $$$N$$$ segments in total.

It is required to find at what distance $$$X$$$ from point $$$A$$$ the last point $$$B_N$$$ is located, that is, the length of segment $$$AB_N$$$. It is guaranteed that $$$X$$$ is an integer.

Input

The first line contains one integer $$$N$$$. The second line contains $$$N$$$ integers separated by spaces — the lengths of the segments $$$c_i$$$.

Output

Print one number $$$X$$$ — the length of segment $$$AB_N$$$.

Scoring

Subtask 1 (up to 20 points): $$$1 \leq N \leq 10, 1 \leq c_i \leq 100$$$

Subtask 2 (up to 20 points): $$$1 \leq N \leq 10, 1 \leq c_i \leq 10^8$$$

Subtask 3 (up to 20 points): $$$1 \leq N \leq 10^4, 1 \leq c_i \leq 10^8$$$

Subtask 4 (up to 20 points): $$$1 \leq N \leq 10, 1 \leq c_i \leq 10^{15}$$$

Subtask 5 (up to 20 points): $$$1 \leq N \leq 10^4, 1 \leq c_i \leq 10^{15}$$$

Examples
Input
2
2 2
Output
3
Input
3
1 1 1
Output
2
Note

An example of a spiral with 2 segments ($$$N = 2$$$) is shown below.

A reminder for Python programmers: you can input a set of space-separated integers like this: 

c = [int(x) for x in input().split()]