Вам даны два массива: массив \(a\), состоящий из \(n\) нулей и массив \(b\), состоящий из \(n\) целых чисел.
Вы можете применить к массиву \(a\) следующую операцию произвольное количество раз: выбрать какой-то подотрезок \(a\) длины \(k\) и добавить арифметическую прогрессию \(1, 2, \ldots, k\) к этому подотрезку — то есть добавить \(1\) к первому элементу подотрезка, \(2\) ко второму элементу и так далее. Выбранный подотрезок должен находиться внутри границ массива \(a\) (если левая граница выбранного подотрезка равна \(l\), тогда должно выполняться условие \(1 \le l \le l + k - 1 \le n\)). Заметьте, что добавляемая прогрессия всегда имеет вид \(1, 2, \ldots, k\), а не \(k, k - 1, \ldots, 1\) или какой-нибудь другой (то есть самый левый элемент всегда увеличивается на \(1\), второй элемент всегда увеличивается на \(2\) и так далее).
Ваша задача — найти минимально возможное количество операций, необходимое для того, чтобы удовлетворить условие \(a_i \ge b_i\) для всех \(i\) от \(1\) до \(n\). Заметьте, что условие \(a_i \ge b_i\) должно быть выполнено для всех элементов сразу.
Выходные данные
Выведите одно целое число — минимально возможное количество операций, необходимое для того, чтобы удовлетворить условие \(a_i \ge b_i\) для всех \(i\) от \(1\) до \(n\).
Примечание
Рассмотрим первый тестовый пример. В этом тесте у нас нет никакого выбора, кроме как добавить пять прогрессий для того, чтобы сделать первый элемент массива равным \(5\). В этом случае массив \(a\) будет равен \([5, 10, 15]\).
Рассмотрим второй тестовый пример. В этом тесте давайте добавим одну прогрессию на отрезке \([1; 3]\) и две прогрессии на отрезке \([4; 6]\). В этом случае массив \(a\) будет равен \([1, 2, 3, 2, 4, 6]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
5 4 6
|
5
|
|
2
|
6 3
1 2 3 2 2 3
|
3
|
|
3
|
6 3
1 2 4 1 2 3
|
3
|
|
4
|
7 3
50 17 81 25 42 39 96
|
92
|