A - <Inversion>

Contest Duration: 2023-11-19(Sun) 12:00 - 2023-11-19(Sun) 14:00 (local time) (120 minutes) Back to Home

A - <Inversion> Editorial

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$

出力

答えを出力せよ．

入力例 1Copy

Copy

4
<><

出力例 1Copy

Copy

$x=(1,2,1,2)$ とすると，これはよい数列です．また， $x$ の転倒数は $1$ です．転倒数が $0$ のよい数列は存在しないので， $1$ が答えになります．

入力例 2Copy

Copy

2
<

出力例 2Copy

Copy

入力例 3Copy

Copy

10
>>>>>>>>>

出力例 3Copy

Copy

入力例 4Copy

Copy

30
<<><>>><><>><><><<>><<<><><<>

出力例 4Copy

Copy

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 1Copy

Copy

4
<><

Sample Output 1Copy

Copy

$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 2Copy

Copy

2
<

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

10
>>>>>>>>>

Sample Output 3Copy

Copy

Sample Input 4Copy

Copy

30
<<><>>><><>><><><<>><<<><><<>

Sample Output 4Copy

Copy