Костя та задачі#11798
Костя проходить послідовність тренувальних занять, кожне з яких полягає у розв’язанні однієї задачі.
Нехай — кількість задач, які він розв’язував. Кожна задача має результат:
— правильне розв’язання,
— помилкове розв’язання.
Послідовність результатів представлена масивом a = (a_1, a_2, \dots, a_n), де a_i \in \{0, 1\}.
Гарантується, що a_n = 1.
За кожний розв’язок Костя отримає певну кількість балів.
Спочатку на рахунку Кості балів, а початковий розмір нарахування або штрафу за розв’язок дорівнює s_1 = 1. Для кожного (1 \le i \le n) оновлення рахунку та s_i відбувається за такими правилами:
Якщо a_i = 1, то до загального рахунку додається s_i, і для наступного завдання встановлюється s_{i+1} = 1.
Якщо a_i = 0, то від загального рахунку віднімається s_i, і для наступного завдання встановлюється s_{i+1} = 2 \cdot s_i.
Потрібно обчислити кінцеву кількість балів після виконання всіх тренувань.
Перший рядок містить ціле число (1 \le n \le 10^5) — кількість задач. Другий рядок містить чисел a_1, a_2, \dots, a_n (a_i \in \{0, 1\}), розділених пробілами.
Виведіть одне ціле число — кінцеву кількість балів після виконання всіх тренувань.
Приклад 1
Розглянемо, як змінюється рахунок Кості на кожному кроці. Спочатку на його рахунку балів, а початкове значення нарахування або штрафу — s_1 = 1. Далі він по черзі розв’язує задачі:
Перша задача (a_1 = 1) — правильна відповідь:
Додаємо s_1 = 1 бал, рахунок стає 0 + 1 = 1.
Оскільки задача розв’язана правильно, встановлюємо s_2 = 1.
Друга задача (a_2 = 0) — неправильна відповідь:
Віднімаємо s_2 = 1 бал, рахунок стає 1 - 1 = 0.
Оскільки відповідь неправильна, наступне штрафне значення подвоюється: s_3 = 2 \cdot s_2 = 2.
Третя задача (a_3 = 0) — неправильна відповідь:
Віднімаємо s_3 = 2 бали, рахунок стає 0 - 2 = -2.
Оскільки відповідь неправильна, наступне штрафне значення подвоюється: s_4 = 2 \cdot s_3 = 4.
Четверта задача (a_4 = 1) — правильна відповідь:
Додаємо s_4 = 4 бали, рахунок стає -2 + 4 = 2.
Оскільки задача розв’язана правильно, встановлюємо s_5 = 1.
П’ята задача (a_5 = 1) — правильна відповідь:
Додаємо s_5 = 1 бал, рахунок стає 2 + 1 = 3.
Завдання закінчилися, тож фінальний рахунок — 3 бали.