Вам дана строка \(s\) длины \(n\), состоящая из символов «+» и «-». По строке \(s\) можно построить массив \(a\) длины \(n\), в котором \(a_i=1\), если \(s_i=\) «+» и \(a_i=-1\), если \(s_i=\) «-».
Чтобы вычислить штраф, нужно выполнить следующие действия:
- Разбить массив \(a\) на непустые массивы \(b_1,b_2,\ldots,b_k\) такие, что \(b_1+b_2+\ldots+b_k=a^\dagger\), где \(+\) обозначает конкатенацию массивов.
- Штраф одного массива — это модуль его суммы, умноженный на его длину. Другими словами, для некоторого массива \(c\) длины \(m\) его штраф вычисляется как \(p(c)=|c_1+c_2+\ldots+c_m| \cdot m\).
- Общий штраф всего массива равняется \(p(b_1)+p(b_2)+\ldots+p(b_k)\).
Найдите минимальный возможный штраф, который вы можете получить, если вы выполните вышеописанные действия оптимально.
\(^\dagger\) Некоторые допустимые способы разбить \(a=[3,1,4,1,5]\) на \((b_1,b_2,\ldots,b_k)\) — \(([3],[1],[4],[1],[5])\), \(([3,1],[4,1,5])\) и \(([3,1,4,1,5])\), в то время как некоторыми недопустимыми способами разбиения \(a\) являются \(([3,1],[1,5])\), \(([3],[\,],[1,4],[1,5])\) и \(([3,4],[5,1,1])\).
Примечание
В первом наборе входных данных \(a=[1]\). Мы можем разбить массив \(a\) на один подмассив \(([1])\). Тогда сумма штрафов равна \(p([1]) = 1\).
Во втором наборе входных данных имеем \(a=[-1,-1,-1,-1,-1]\). Мы можем разбить массив \(a\) на массивы \(([-1],[-1],[-1],[-1],[-1])\). Тогда сумма штрафов подмассивов равна \(p([-1]) + p([-1]) + p([-1]) + p([-1]) + p([-1]) = 1 + 1 + 1 + 1 + 1 = 5\).
В третьем наборе входных данных \(a=[1,-1,1,-1,1,-1]\). Мы можем разбить массив \(a\) на \(([1,-1,1,-1],[1,-1])\). Тогда сумма штрафов подмассивов равна \(p([1,-1,1,-1]) + p([1,-1]) = 0 + 0 = 0\).