Question
Sequence Snap
Lila is given a pattern string Q of length M - 1, made up of the characters '<' and '>'.
She wants to create a sequence of M non-negative integers (S[0], S[1], ..., S[M-1]) such that:
-
For each index
ifrom0toM - 2:-
If
Q[i] == '<', thenS[i] < S[i + 1] -
If
Q[i] == '>', thenS[i] > S[i + 1]
-
Out of all sequences that satisfy this condition, Lila wants the one with the smallest total sum.
Your task is to find and return that minimum possible sum.
Input
The first line of the input contains a single integer M.
The second line of the input contains a string of size M-1.
The second line of the input contains a string of size M-1.
Output
Find the beautiful sequence with the minimum sum of its elements and print this sum.
Example
Sample Input
4
<>>
Sample Output
3
Explanation
One such sequence with sum = 3 is [0, 2, 1, 0]
It can be verified that no smaller sum can be obtained while satisfying the conditions for beautiful sequence.
4
<>>
Sample Output
3
Explanation
One such sequence with sum = 3 is [0, 2, 1, 0]
It can be verified that no smaller sum can be obtained while satisfying the conditions for beautiful sequence.