问题描述
给定一个长度为n的正整数序列 A.
你需要对序列 A 同时满足以下两个条件的非空子序列 B 计数：
B 序列的顺序对数等于逆序对数。
$\forall 1 \le i \lt j \le |B|,Bi^{Bj} \lt Bj^{Bi}$。
输出满足条件的 B 序列数量对 998244353 取模的值即可。
输入格式
第一行一个整数，表示 n。
接下来一行 n 个数，第 i 个数表示 Ai。
输出格式
输出一行一个数表示答案。
输入输出样例 1
输入样例
7 4 1 5 4 6 3 3输出样例
9输入输出样例 2
输入样例
16 3 2 6 16 1 4 1 4 4 5 3 1 4 4 3 15输出样例
20
样例
特殊性质 A：保证序列中不同的数不超过 5 种。
特殊性质 B：保证 $\forall 1 \le i \lt j \le |A|,Ai^{Aj}\le Aj^{Ai}$。
对于100%的数据满足：$1\le n \le 10^6,1\le Ai\le n$。
约定和数据范围
| 测试点编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $n\le$ | 10 | 300 | 300 | 2000 | 2000 | $10^6$ | $10^6$ | $10^6$ | $10^6$ | $10^6$ |
| 特殊性质 | 无 | 无 | 无 | 无 | 无 | A | B | 无 | 无 | 无 |