I'm praying for owning a transparent heart; as well as eyes with tears more than enough...
Ирис посмотрела на звезды, и в её голове возникла прекрасная задача. Она приглашает вас решить её, чтобы можно было предсказать метеоритный дождь.
На небе есть \(n\) звезд, расположенных в ряд. У Ирис есть телескоп, с помощью которого она смотрит на них.
Изначально Ирис наблюдает за звездами в отрезке \([1, n]\), и у неё есть значение удачи, равное \(0\). Ирис хочет найти центральную звезду для каждого отрезка \([l, r]\), за которым она наблюдает. Она использует следующую рекурсивную процедуру:
- Сначала она вычисляет \(m = \left\lfloor \frac{l+r}{2} \right\rfloor\).
- Если длина отрезка (т.е. \(r - l + 1\)) чётная, Ирис разделяет его на два отрезка одинаковой длины \([l, m]\) и \([m+1, r]\) для дальнейшего наблюдения.
- В противном случае Ирис наведёт телескоп на звезду \(m\), и её значение удачи увеличится на \(m\); далее, если \(l \neq r\), Ирис продолжит наблюдать за двумя отрезками \([l, m-1]\) и \([m+1, r]\).
Ирис немного ленива. Она определяет свою лень целым числом \(k\): по мере продвижения наблюдения она не станет наблюдать за отрезком \([l, r]\), если его длина строго меньше \(k\). Пожалуйста, предскажите её итоговое значение удачи.
Выходные данные
Для каждого набора входных данных выведите одно целое число — итоговое значение удачи.
Примечание
В первом наборе входных данных, в начале Ирис наблюдает за отрезком \([1, 7]\). Поскольку у \([1, 7]\) нечётная длина, она наводит телескоп на звезду \(4\) и, следовательно, увеличивает своё значение удачи на \(4\). Затем отрезок разбивается на \(2\) новых отрезка: \([1, 3]\) и \([5, 7]\). Отрезок \([1, 3]\) снова имеет нечётную длину, поэтому Ирис прицеливается на звезду \(2\) и увеличивает своё значение удачи на \(2\). Затем он разбивается на \(2\) новых отрезка: \([1, 1]\) и \([3, 3]\), оба из которых имеют длину меньше \(2\), поэтому дальнейшее наблюдение не проводится. Что касается отрезка \([5, 7]\), то прогресс аналогичен, и значение удачи увеличивается на \(6\). Следовательно, итоговое значение удачи равняется \(4 + 2 + 6 = 12\).
В последнем наборе входных данных, Ирис в итоге понаблюдает за всеми звёздами, и итоговым значением удачи будет \(1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
7 2
11 3
55 13
5801 6
8919 64
8765432 1
|
12
18
196
1975581
958900
38416403456028
|