Semi-Permutations

2 secs 1024 MB
eSeF

問題文


蝉のセミくんは、以下の条件を満たす数列 準順列 と定義することにしました。

  • ある 以上の整数 が存在して、数列 から要素を1つだけ消去し、それを並び替えることによって を作ることができる。

なお、上記の定義から空の数列 も準順列であることに注意してください。

長さ の数列 が与えられるので、 の連続とは限らない部分列であって、準順列であるようなものの個数を で割ったあまりを求めてください。

入力



制約


  • 入力は全て整数

出力


答えを で出力してください。

入力例1

3
3 1 4
出力例1

4

の4つが準順列になっています。
例えば、 とし、 から を消去して並び替えることで得られます。

入力例2

4
3 4 3 5
出力例2

1

条件を満たす部分列は のみです。

入力例3

17
5 2 7 7 1 6 3 1 5 3 6 1 6 3 4 2 4
出力例3

2511

提出


Go (1.14)