Unique Subsequence

时间限制：2s
空间限制：1024MB

题目描述

给定长度为 $N$ 的整数序列 $A_1,A_2,\ldots,A_N$。

求 $A$ 的所有非空子序列 $s$ 中，恰好只有一种下标选择方法能取出 $s$ 的序列数量，并对 $998244353$ 取模。

更形式化地说，若 $s=(s_1,\ldots,s_k)$，要求恰好存在一组下标 $1\le idx(1)<\cdots<idx(k)\le N$，满足对每个 $i$ 都有 $A_{idx(i)}=s_i$。

输入格式

第一行输入整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出答案对 $998244353$ 取模后的值。

样例输入 1

3
1 2 1

样例输出 1

5

样例输入 2

4
4 2 1 3

样例输出 2

15

样例输入 3

12
1 2 3 6 9 2 3 3 9 6 1 6

样例输出 3

1178

数据范围

对于所有数据，$1\le N\le2\times10^5$，$1\le A_i\le N$。