4406 构造B数组
时间限制2 S
内存限制128 MB
通过率50%(4 / 8)
题目描述
本题将给你一个整数数组 a , 其长度为 m。
需要你根据以下几个条件构造出数组 b ：
- 长度为 m ，且都为整数。
- b 数组首项为 0。
- 对于任意一对索引 i 和 j（1 ≤ i, j ≤ m），如果 ai = aj 则 bi = bj（注意，如果 ai ≠ aj，则 bi 和 bj 相等与否随意）。
- 对于任意索引 i（i∈[1, m−1]），要么使得 bi = bi+1，要么使得 bi + 1 = bi + 1。
请你计算出所有可以根据上述条件构造出的数组 b 的数量。
输入格式
第一行包含一个整数 m。
第二行包含 n 个整数 a1, a2, …, am。
输出格式
一个整数，由于答案可能很大，你只需要输出对 998244353 取模后的结果。
输入输出样例
输入复制
5
1 2 1 2 3输出复制
2数据范围与提示
所有测试点满足 2 ≤ m ≤ 2×105，1 ≤ ai ≤ 109。
例如，如果 a=[1, 2, 1, 2, 3]，则一共有 2 个满足条件的数组 b，分别是 b=[0,0,0,0,0] 和 b=[0,0,0,0,1]。
例如，如果 a=[1, 2, 1, 2, 3]，则一共有 2 个满足条件的数组 b，分别是 b=[0,0,0,0,0] 和 b=[0,0,0,0,1]。
输入样例2：
2 100 1
输出样例2：
2
输入样例3：
4 1 3 3 7
输出样例3：
4
来源