Бананистан — прекрасная банановая республика. Прекрасные женщины в прекрасных платьях. Прекрасные статуи прекрасных воевод. Прекрасные звезды прекрасными ночами.
Народ в Бананистане любит играть в одну чудаковатую игру — Лампо. Дан массив лампочек, у игрока есть позиция напротив одной из этих лампочек. Расстояние между соседними лампочками равно 1. На каждом ходу игрок может переместиться в любую позицию, получив за это |posnew - posold| очков штрафа. После этого загорается некоторое множество подряд идущих лампочек, а игрок получает штраф, равный расстоянию до ближайшей горящей лампочки. Затем все лампочки выключаются. Задача — минимизировать общий штраф, полученный во время игры. Уверяю вас, бананистанцы ночи напролет играют в лампочки.
Приближается день банана и Вас наняли, чтобы сыграть самую прекрасную партию в Лампо в истории. Уже установили гигантский массив лампочек, вы знаете свое начальное положение и какие лампочки будут загораться на каждом ходу. Вам надо сыграть идеальную игру и впечатлить бананистанцев и их родных.
Выходные данные
В выходе должно быть записано единственное число, обозначающее лучший результат (минимальный штраф), который можно получить, играя в Лампо.
Примечание
До 1-го хода перейдите в положение 5.
До 2-го хода перейдите в положение 9.
До 5-го хода перейдите в положение 8.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
2 7
9 16
8 10
9 17
1 6
|
8
|