Дан массив \(a\), состоящий из \(n\) положительных целых чисел, и массив \(b\) размера \(n\). Изначально \(b_i=0\) для каждого \(1 \leq i \leq n\).
За один ход вы можете выбрать целое число \(i\) (\(1 \leq i \leq n\)) и прибавить \(a_i\) к \(b_i\) или вычесть \(a_i\) из \(b_i\). За какое минимальное число ходов можно сделать \(b\) возрастающим (то есть таким, что каждый элемент строго больше всех предыдущих)?
Выходные данные
Выведите одно целое число — минимальное число ходов, за которое можно сделать \(b\) возрастающим.
Примечание
Пример \(1\): можно вычесть \(a_1\) из \(b_1\), и прибавить \(a_3\), \(a_4\), \(a_5\) к \(b_3\), \(b_4\) и \(b_5\) соответственно. В итоге получим массив [\(-1\), \(0\), \(3\), \(4\), \(5\)] за \(4\) хода.
Пример \(2\): можно получить массив [\(-3\), \(-2\), \(-1\), \(0\), \(1\), \(2\), \(3\)] за \(10\) ходов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
|
4
|
|
2
|
7
1 2 1 2 1 2 1
|
10
|
|
3
|
8
1 8 2 7 3 6 4 5
|
16
|