一条录音被记为整数序列 a_1,a_2,…,a_n，相同整数表示相同声音。

对一段录音，可以执行以下操作任意多次：选择当前相邻且数值相同的两个元素，将这两个元素一起删除。删除后，两侧剩余部分重新相邻。

你要把原序列切成若干个非空连续块。每一块必须能够通过零次或多次上述操作，恰好留下一个元素。

求合法切法的数量，对 998244353 取模。

切法只由哪些相邻位置之间设置了切口决定。同一切法采用不同的删除顺序，或者留下不同位置上的元素，都不会产生新的切法。不同块之间不能进行删除操作。

输入格式

本题只有一组输入数据。

第一行包含一个整数 n。

第二行包含 n 个整数 a_1,a_2,…,a_n。

输出格式

输出合法切法数量对 998244353 取模的结果。

数据范围

• 1 ≤ n ≤ 200000；
• 1 ≤ a_i ≤ 10^9。

样例 1

4
1 2 2 1

3

说明：三种切法是：

[1] [2] [2] [1]
[1 2 2] [1]
[1] [2 2 1]

整个序列会消为空，不能作为一个合法块。

样例 2

3
1 2 1

1

说明：只有把每个元素单独放入一块的切法合法。

下载样例数据