002 - Increasing Sequence

時間制限 2 秒 / メモリ制限 256 MB / 得点 200 / x 2 /


TLE
2sec
MLE
256MB
得点
200

問題

長さ$ \ N \ $の数列$ \ A = (a_1,a_2,\ldots,a_N) \ $が与えられます。
この数列から$ \ 1 \ $つ以上の要素を選び、並べ替えることで広義単調増加の数列を作ることにします。
作ることのできる数列は何通りあるでしょうか?$ \ 998244353 \ $で割った余りを求めてください。

なお、数列$ \ B = (b_1,b_2,\ldots,b_m) \ $が$ \ b_1 \leq b_2 \leq \ldots \leq b_m \ $を満たすとき、この数列は広義単調増加であるといいます。

入力

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

$N$
$a_1 \ a_2 \ldots a_N$

出力

答えを$ \ 998244353 \ $で割った余りを出力せよ。出力の末尾には改行を入れること。

制約

  • $1 \leq N \leq 10^5$
  • $1 \leq a_i \leq 10^5 \ (1 \leq i \leq N) \ $
  • 入力は全て整数

入出力例

入力例1

3
2 1 2

出力例1

5

次の$ \ 5 \ $通りがあります。

  • $(1)$
  • $(2)$
  • $(1,2)$
  • $(2,2)$
  • $(1,2,2)$

入力例2

5
3 1 2 2 1

出力例2

17