Home

Problem Statement

Given is a string $S$ of length $N-1$. Each character in $S$ is < or >.

A sequence of $N$ non-negative integers, $a_1,a_2,\cdots,a_N$, is said to be good when the following condition is satisfied for all $i$ ($1 \leq i \leq N-1$):

• If $S_i=$ <: $a_i<a_{i+1}$
• If $S_i=$ >: $a_i>a_{i+1}$

Find the minimum possible sum of the elements of a good sequence of $N$ non-negative integers.

Constraints

• $2 \leq N \leq 5 \times 10^5$
• $S$ is a string of length $N-1$ consisting of < and >.

Sample Input 1

<>>

Sample Output 1

3

$a=(0,2,1,0)$ is a good sequence whose sum is $3$. There is no good sequence whose sum is less than $3$.

Sample Input 2

<>>><<><<<<<>>><

Sample Output 2

28