Джон отважно боролся за спасение одичалых, атакованных белыми ходоками в Суровом Доме. По прибытию Сэм говорит, что хочет направиться в Старомест, чтобы тренироваться в Цитадели и стать мейстером. Так он сможет вернуться и занять место покойного Эймона, как мейстер Черного Замка. Джон согласился с предложением Сэма, и Сэм отправляется в свое путешествие в Цитадель. Однако становление учащимся Цитадели не так легко, и поэтому мейстеры в Цитадели предложили Сэму задачу, чтобы протестировать его соответствие требованиям.
Изначально у Сэма есть список с единственным числом n. Далее он выполняет некоторые операции над этим списком. На каждой операции Сэм должен удалить любой такой элемент x, что x > 1, из списка, и вставить вместо него три новых элемента 
, 
, последовательно. Он должен делать эти операции до тех пор, пока все элементы в списке не равны 0 или 1.
Теперь мейстеры хотят знать общее число единиц на позициях с l-й по r-ю в списке. Сэм хочет стать великим мейстером, но, к сожалению, он не может решить эту задачу. Можете ли вы помочь Сэму пройти тест на соответствие?
Выходные данные
Выведите общее число единиц на позициях с l-й по r-ю в получившемся списке.
Примечание
Рассмотрим первый тестовый пример:
Список чисел со 2-й по 5-ю позиции содержит числа [1, 1, 1, 1]. Количество единиц равно 4.
Второй тестовый пример:
Список чисел с 3-й по 10-ю позиции содержит числа [1, 1, 1, 0, 1, 0, 1, 0]. Количество единиц равно 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2 5
|
4
|
|
2
|
10 3 10
|
5
|