Trout IV

Hint: This task is only thematically related to the previous Trout tasks.

Having successfully set up a spy communication network, the Trout are now looking to communicate their strategy for world domination across the globe. To this end, the Trout have developed the Trout Communication Protocol (TCP). The Trout have encoded a single integer into a sequence of $N$ integers $v_1, v_2, \dots, v_N$.

Decoding the message works as follows: you initially start with zero, then in the $i$-th step (starting from $i = 1$):

• If $i$ is odd then you add $v_i$
• If $i$ is even then you subtract $v_i$

The Trout have asked for your help to write a program to decode the encrypted message. It is somewhat difficult to tell how conquering the entire planet will impact the Trout population.

Input

The first line contains the single integer $N$.

The following $N$ lines each contain a single integer, $v_i$, which is the $i$-th number in the encoded message.

Output

Output a single integer, the decoded message.

Constraints

• $1 \le N \le 100,000$, that is, the encoded message consists of at most $100$ thousand integers.
• $-10,000,000 \le v_i \le 10,000,000$: that is, all numbers in the encoded message are between negative $10$ million and positive $10$ million.
• The decoded message is guaranteed to be in the range $-10^9$ to $10^9$ at every step of the decoding process.

Subtasks

• Subtask 1 (+33%): $N = 4$, that is, the encoded message consists of exactly four integers.
• Subtask 2 (+29%): $N$ is even.
• Subtask 3 (+38%): No further constraints.

Sample Explanations

Sample 1

In this sample the encrypted message consists of $N = 4$ integers. We can decode the number as $14 - 6 + 19 - 7 = 20$.