[ARC168A] <Inversion>
题意翻译
给定一个长度为 $N-1$ 的字符串 $S$ 来表示长度为 $N$ 的序列 $x$ 对于 $s[i] (1 \le i\le N-1)$，当 $s[i]$ 为字符 $<$ 时，表示 $x[i]<x[i+1]$ , 反之同理。
求字符串能表示的序列中 **逆序对** 总数的最小值。
翻译by 715279
题目描述
[problemUrl]: https://atcoder.jp/contests/arc168/tasks/arc168_a
`<`, `>` からなる長さ $ 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\ )\ であって，x_i\ >\ x_j $ を満たすものの個数です．
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる．
> $ N $ $ S $
输出格式
答えを出力せよ．
输入输出样例
输入样例 #1
4
<><输出样例 #1
1输入样例 #2
2
<输出样例 #2
0输入样例 #3
10
>>>>>>>>>输出样例 #3
45输入样例 #4
30
<<><>>><><>><><><<>><<<><><<>输出样例 #4
19说明
### 制約
- $ 2\ \leq\ N\ \leq\ 250000 $
- $ S $ は `<`, `>` からなる長さ $ N-1 $ の文字列．
- 入力される値はすべて整数．
### Sample Explanation 1
$ x=(1,2,1,2) $ とすると，これはよい数列です． また，$ x $ の転倒数は $ 1 $ です． 転倒数が $ 0 $ のよい数列は存在しないので，$ 1 $ が答えになります．