1635 - Numeric and Lexicographic order

時間制限 2 秒 / メモリ制限 1024 MB / 得点 5 / Writer ei1903 / x 1 / 統計 /


TLE
2sec
MLE
1024MB
得点
5

問題

長さ$ \ N \ $の整数列$ \ (a_1,a_2,\ldots,a_N) \ $が与えられます。次の条件をすべて満たす整数の組$ \ (i,j) \ $の個数を求めてください。

  • $1 \leq i \lt j \leq N$
  • $a_i \lt a_j$
  • $a_i,a_j \ $を文字列としてみたとき、$a_i \ $は$ \ a_j \ $より辞書順で小さい

入力

入力は以下の形式で標準入力から与えられる。

$N$
$a_1 \ a_2 \ \ldots \ a_N$

出力

答えを出力せよ。出力の末尾には改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $2 \leq N \leq 3 \times 10^5$
  • $0 \leq a_i \leq 10^9$
  • $a_i \neq a_j \ (i \neq j)$
  • 入力は全て整数

入出力例

入力例1

5
21 3 14 27 5

出力例1

3

$(1,4),(2,5),(3,4) \ $が条件を満たす。


入力例2

3
2 1 0

出力例2

0

条件を満たす組は存在しない。