Дан массив \(a\) длины \(n\). Чтобы вычислить штраф, нужно выполнить следующие действия:
- Разбить массив \(a\) на две (возможно, пустых) подпоследовательности \(^\dagger\) \(s\) и \(t\) такие, что каждый элемент \(a\) находится либо в \(s\), либо в \(t^\ddagger\).
- Для массива \(b\) длины \(m\) определим штраф \(p(b)\) массива \(b\) как количество индексов \(i\) между \(1\) и \(m - 1\) таких, что \(b_i < b_{i + 1}\).
- Общий штраф, который вы получите, равен \(p(s) + p(t)\).
Найдите минимально возможный штраф, который вы получите, если выполните вышеописанные действия оптимально.
\(^\dagger\) Последовательность \(x\) является подпоследовательностью \(y\), если \(x\) может быть получена из \(y\) удалением нескольких (возможно, ни одного или всех) элементов.
\(^\ddagger\) Некоторыми допустимыми способами разбиения массива \(a=[3,1,4,1,5]\) на \((s,t)\) являются \(([3,4,1,5],[1])\), \(([1,1],[3,4,5])\) и \(([\,],[3,1,4,1,5])\), в то время как некоторыми недопустимыми способами разбиения \(a\) являются \(([3,4,5],[1])\), \(([3,1,4,1],[1,5])\) и \(([1,3,4],[5,1])\).
Примечание
В первом наборе входных данных возможный способ разбиения \(a\) — \(s=[2,4,5]\) и \(t=[1,3]\). Штраф равняется \(p(s)+p(t)=2 + 1 =3\).
Во втором наборе входных данных возможный способ разбиения \(a\) — \(s=[8,3,1]\) и \(t=[2,1,7,4,3]\). Штраф равняется \(p(s)+p(t)=0 + 1 =1\).
В третьем наборе входных данных возможным способом разбиения \(a\) является \(s=[\,]\) и \(t=[3,3,3,3,3]\). Штраф равняется \(p(s)+p(t)=0 + 0 =0\).