Kostya and Problems#11798
Sign in

Kostya and Problems

1 second
256 megabytes
Very easy

Kostya is going through a series of training sessions, each of which involves solving one problem.

Let be the number of problems he has solved. Each problem has a result:

The sequence of results is represented by an array a = (a_1, a_2, \dots, a_n), where a_i \in \{0, 1\}.

It is guaranteed that a_n = 1.

For each solution, Kostya receives a certain number of points.

Initially, Kostya has points on his account, and the initial amount of addition or penalty for a solution is s_1 = 1. For each (1 \le i \le n), the update of the account and s_i occurs according to the following rules:

You need to calculate the final number of points after completing all training sessions.

Input

The first line contains an integer (1 \le n \le 10^5) — the number of problems. The second line contains numbers a_1, a_2, \dots, a_n (a_i \in \{0, 1\}), separated by spaces.

Output

Print one integer — the final number of points after completing all training sessions.

Examples

Example 1

Loading
Loading

Note

Let's see how Kostya's account changes at each step. Initially, his account has points, and the initial value of addition or penalty is s_1 = 1. Next, he sequentially solves the problems:

  • First problem (a_1 = 1) — correct answer:

    • Add s_1 = 1 point, the account becomes 0 + 1 = 1.

    • Since the problem is solved correctly, set s_2 = 1.

  • Second problem (a_2 = 0) — incorrect answer:

    • Subtract s_2 = 1 point, the account becomes 1 - 1 = 0.

    • Since the answer is incorrect, the next penalty value doubles: s_3 = 2 \cdot s_2 = 2.

  • Third problem (a_3 = 0) — incorrect answer:

    • Subtract s_3 = 2 points, the account becomes 0 - 2 = -2.

    • Since the answer is incorrect, the next penalty value doubles: s_4 = 2 \cdot s_3 = 4.

  • Fourth problem (a_4 = 1) — correct answer:

    • Add s_4 = 4 points, the account becomes -2 + 4 = 2.

    • Since the problem is solved correctly, set s_5 = 1.

  • Fifth problem (a_5 = 1) — correct answer:

    • Add s_5 = 1 point, the account becomes 2 + 1 = 3.

    • Tasks are finished, so the final account is 3 points.