A supply convoy's manifest lists the weight of each crate in the order the crates are loaded onto the truck. As part of a balance-inspection protocol, an auditor examines every contiguous stretch of crates whose length is odd (a single crate, three crates in a row, five in a row, and so on) and adds up the weights within that stretch. Two stretches of the same length starting at different positions are both examined separately, even if their weights happen to be identical. The auditor wants the grand total obtained by summing the stretch-total of every such odd-length stretch that appears anywhere in the manifest.

Input format

• Line 1: a single integer n, the number of crates.
• Line 2: n space-separated integers, the weight of each crate in loading order.

Output format

Print a single integer: the sum, over every contiguous odd-length stretch of crates, of the total weight of that stretch.

Constraints

• 1 <= n <= 1000
• 1 <= weight of each crate <= 1000

5
1 4 2 5 3

58

2
1 2

3