Люк любит поесть. Перед ним \(n\) стопок еды, выстроенных по прямой линии. В \(i\)-й стопке находится \(a_i\) единиц еды.
Люк будет идти от \(1\)-й стопки к \(n\)-й стопке, и он хочет съесть каждую стопку еды, не возвращаясь назад. Когда Люк достигает \(i\)-й стопки, он может съесть ее тогда и только тогда, когда \(|v - a_i| \leq x\), где \(x\) — фиксированное целое число, а \(v\) — пищевое желание Люка.
Прежде чем Люк начнет ходить, он может установить \(v\) в любое целое число. Кроме того, для каждого \(i\) (\(1 \leq i \leq n\)) Люк может изменить свое пищевой желание на любое целое число до того, как он съест \(i\)-ю стопку.
Найдите минимальное количество изменений, необходимое для того, чтобы съесть каждую стопку еды.
Обратите внимание, что первоначальный выбор \(v\) не считается изменением.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите целое число — минимальное количество необходимых изменений.
Примечание
В первом наборе входных данных Люк может установить \(v\) в \(5\) до того, как он начнет ходить. И он может идти прямо, чтобы съесть каждую стопку еды, не меняя \(v\).
Во втором наборе входных данных Люк может установить \(v\) в \(3\) до того, как он начнет ходить. И он может поменять \(v\) на \(10\), прежде чем съест вторую стопку. После этого он может идти прямо, чтобы съесть оставшуюся еду, не меняя \(v\).
В четвертом наборе входных данных Люк может установить \(v\) в \(3\) до того, как начнет ходить. И он может поменять \(v\) на \(8\) до того, как съест шестую стопку. После этого он может идти прямо, чтобы съесть оставшуюся еду, не меняя \(v\).
В пятом наборе входных данных Люк может установить \(v\) в \(4\) до того, как начнет ходить. И он может поменять \(v\) на \(6\) до того, как съест четвертую стопку. Тогда он может поменять \(v\) на \(12\) до того, как съест седьмую стопку. После этого он может идти прямо, чтобы съесть оставшуюся еду, не меняя \(v\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5 3
3 8 5 6 7
5 3
3 10 9 8 7
12 8
25 3 3 17 8 6 1 16 15 25 17 23
10 2
1 2 3 4 5 6 7 8 9 10
8 2
2 4 6 8 6 4 12 14
8 2
2 7 8 9 6 13 21 28
15 5
11 4 13 23 7 10 5 21 20 11 17 5 29 16 11
|
0
1
2
1
2
4
6
|