Дана строка \(s\) из \(n\) символов, каждый из которых — либо <, либо >.
Массив \(a\), состоящий из \(n+1\) элементов, является совместимым со строкой \(s\), если для каждого \(i\) от \(1\) до \(n\) символ \(s_i\) соответствует результату сравнения элементов \(a_i\) и \(a_{i+1}\), то есть:
- \(s_i\) равен < тогда и только тогда, когда \(a_i < a_{i+1}\);
- \(s_i\) равен > тогда и только тогда, когда \(a_i > a_{i+1}\).
Например, массив \([1, 2, 5, 4, 2]\) совместим со строкой <<>>. С этой строкой совместимы и некоторые другие массивы, например, \([13, 37, 42, 37, 13]\).
Стоимостью массива назовем количество различных элементов в нем. Например, стоимость \([1, 2, 5, 4, 2]\) равна \(4\); стоимость массива \([13, 37, 42, 37, 13]\) равна \(3\).
Вы должны посчитать минимальную стоимость среди всех массивов, совместимых со строкой \(s\).
Примечание
В первом наборе входных данных примера из условия один из возможных массивов — это \([13, 37, 42, 37, 13]\).
Во втором наборе входных данных примера из условия один из возможных массивов — это \([42, 37, 13, 37, 42]\).