Вам задан массив \(a\) длины \(n\), состоящий из положительных целых чисел.
Вы можете применять следующую операцию любое количество раз (возможно, ноль раз):
- выбрать три целых числа \(l\), \(r\) и \(x\), для которых \(1 \le l \le r \le n\), и умножить каждое \(a_i\), для которого \(l \le i \le r\), на \(x\).
Обратите внимание, что вы можете выбрать любое целое число \(x\), не обязательно положительное.
Вам нужно определить минимальное число таких операций, за которое вы можете сделать массив \(a\) отсортированным строго в порядке возрастания (т. е. должно выполняться условие \(a_1 < a_2 < \dots < a_n\)).
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество операций, необходимых для превращения массива \(a\) в отсортированный в порядке возрастания массив.
Примечание
В первом наборе входных данных мы можем выполнять следующие операции:
- \(l = 2\), \(r = 4\), \(x = 3\);
- \(l = 4\), \(r = 4\), \(x = 2\);
- \(l = 5\), \(r = 5\), \(x = 10\).
После этих операций массив
\(a\) превратится в
\([1, 3, 6, 12, 20]\).
Во втором наборе входных данных мы можем выполнять следующие операции:
- \(l = 1\), \(r = 4\), \(x = -2\);
- \(l = 6\), \(r = 6\), \(x = 1337\).
После этих операций массив
\(a\) превратится в
\([-10, -8, -6, -4, 5, 1337]\).
В третьем наборе входных данных массив \(a\) уже отсортирован.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
1 1 2 2 2
6
5 4 3 2 5 1
3
1 2 3
|
3
2
0
|