Question
Sum Slope
Ram is given a string P of length N-1 (1-indexed), where each Pi is either '<' or '>'. He seeks a sequence of N non-negative integers deemed beautiful, satisfying: for every i from 1 to N - 1, if Pi == '>', then Ai > Ai+1; if Pi == '<', then Ai < Ai+1.
Among all such sequences, find the one with the smallest sum of elements and return that sum.
Input
The first line of the input contains a single integer N.
The second line of the input contains a string of size N-1.
The second line of the input contains a string of size N-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.