/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
<, > からなる長さ N-1 の文字列 S が与えられます．
長さ N の数列 x=(x_1,x_2,\cdots,x_N) が以下の条件を満たすとき，それをよい数列と呼ぶことにします．
- 各 i (1 \leq i \leq N-1) について，S の i 文字目が
<なら x_i\lt x_{i+1} で，>なら x_i \gt x_{i+1}．
よい数列の転倒数としてあり得る最小値を求めてください．
数列の転倒数とは
長さ n の数列 x=(x_1,x_2,\cdots,x_n) の転倒数とは，整数の組 (i,j) (1 \leq i < j \leq n) であって，x_i>x_j を満たすものの個数です．
制約
- 2 \leq N \leq 250000
- S は
<,>からなる長さ N-1 の文字列． - 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N S
出力
答えを出力せよ．
入力例 1
4 <><
出力例 1
1
x=(1,2,1,2) とすると，これはよい数列です． また，x の転倒数は 1 です． 転倒数が 0 のよい数列は存在しないので，1 が答えになります．
入力例 2
2 <
出力例 2
0
入力例 3
10 >>>>>>>>>
出力例 3
45
入力例 4
30 <<><>>><><>><><><<>><<<><><<>
出力例 4
19
Score : 300 points
Problem Statement
You are given a string S of length N-1 consisting of < and >.
A sequence x=(x_1,x_2,\cdots,x_N) of length N is called a good sequence if and only if it satisfies the following condition:
- For each i (1 \leq i \leq N-1), if the i-th character of S is
<, then x_i\lt x_{i+1}; if it is>, then x_i \gt x_{i+1}.
Find the minimum possible inversion number of a good sequence.
What is the inversion number of a sequence?
The inversion number of a sequence x=(x_1,x_2,\cdots,x_n) of length n is the number of pairs of integers (i,j) (1 \leq i < j \leq n) such that x_i>x_j.
Constraints
- 2 \leq N \leq 250000
- S is a string of length N-1 consisting of
<and>. - All input values are integers.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
4 <><
Sample Output 1
1
x=(1,2,1,2) is a good sequence, and its inversion number is 1. There is no good sequence whose inversion number is 0, so the answer is 1.
Sample Input 2
2 <
Sample Output 2
0
Sample Input 3
10 >>>>>>>>>
Sample Output 3
45
Sample Input 4
30 <<><>>><><>><><><<>><<<><><<>
Sample Output 4
19