| На своей апельсиновой плантации мужчина из Флориды получает очередное спам-письмо, доставленное вороной. Естественно, он отправляет его обратно самым неудобным из возможных способов. |
Ворона сидит на позиции \(0\) числовой прямой. Есть \(n\) пугал, расположенных на целочисленных координатах \(a_1, a_2, \ldots, a_n\) вдоль числовой прямой. Эти пугала были зачарованы, что позволяет им перемещаться влево и вправо со скоростью \(1\) единица в секунду.
Ворона боится пугал и хочет держаться на расстоянии по крайней мере \(k\) от ближайшего пугала, расположенного на позиции вороны или левее. Для этого ворона использует свою способность к телепортации следующим образом:
- Пусть \(x\) — текущее положение вороны, а \(y\) — максимальная координата пугала, такая, что \(y \le x\). Если \(x - y < k\), то есть пугало находится слишком близко, то ворона мгновенно телепортируется на позицию \(y + k\).
Эта телепортация происходит мгновенно и непрерывно. Ворона будет продолжать проверять, нет ли пугал, расположенных на её позиции или слева от неё, и телепортироваться всякий раз, когда кто-то подойдет слишком близко (что может произойти в нецелый момент времени). Обратите внимание, что помимо телепортации, ворона не будет передвигаться сама по себе.
Ваша задача состоит в том, чтобы определить минимальное время, необходимое для того, чтобы ворона оказалась на позиции, большей или равной \(\ell\). При этом пугала двигаются оптимально, чтобы позволить вороне достичь своей цели. Для удобства мы просим вывести значение, вдвое больше минимального времени, необходимого вороне для достижения целевой позиции \(\ell\). Можно доказать, что это значение всегда будет целым числом.
Обратите внимание, что пугала могут стартовать, останавливаться или менять направление в любой момент (возможно, в нецелые моменты времени).
Выходные данные
Для каждого набора входных данных выведите одно целое число, представляющее удвоенное минимальное время, необходимое вороне для телепортации в положение, большее или равное \(\ell\).
Примечание
В первом наборе входных данных ворона мгновенно телепортируется на позицию \(3\) из-за пугала на позиции \(0\). Затем это пугало может переместиться на позицию \(2\), заставляя ворону непрерывно постепенно перемещаться из положения \(3\) в положение \(5\), завершая путешествие за \(2\) секунды. Следовательно, ответ равен \(4\).
Во втором наборе входных данных пугало \(1\) и пугало \(2\) могут переместиться на позиции \(0\) и \(3\) соответственно за \(2\) секунды, в то время как пугало \(3\) остается на позиции \(5\). Ворона телепортируется на позицию \(2\) благодаря пугалу \(1\). Затем пугало \(1\) перемещается вправо, в то время как пугало \(2\) и пугало \(3\) перемещаются влево в течение \(0.5\) секунд. Это приводит к тому, что ворона непрерывно перемещается из положения \(2\) в положение \(2.5\) из-за того, что пугало \(1\) перемещается вправо из положения \(0\). По истечении этой половины секунды пугала окажутся на позициях \(0.5, 2.5, 4.5\). Пугало \(2\), теперь находящееся на позиции \(2.5\), заставляет ворону мгновенно телепортироваться на позицию \(4.5\), а пугало \(3\) на позиции \(4.5\) заставляет её мгновенно телепортироваться на позицию \(6.5\), что превосходит \(\ell = 5\). Таким образом, ворона завершает перемещение за \(2.5\) секунды, а ответ равен \(5\).
Можно показать, что это минимально возможное время для обоих наборов входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
1 3 5
0
3 2 5
2 5 5
1 10 10
10
10 1 10
0 1 2 3 4 5 6 7 8 9
2 1 2
0 0
2 1 2
0 2
2 1 3
0 2
2 2 4
1 1
9 12 54
3 3 8 24 25 27 29 34 53
|
4
5
20
0
2
1
2
2
7
|