← 返回题目列表

AtCoder · arc159_f

F. 好师

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

一个序列 X 被称为 好 当以下成立时。

  • X 可以通过重复以下操作零次或多次来清空。
    • 删除两个相邻元素 x_i 和 x_{i+1} of X 这样 x_i \neq x_{i+1}.

给你一个序列 2N 元素: A=(a_1,\ldots,a_{2N}).
其中 2^{2N-1} 划分方法 A 到一个或多个连续的子序列中,有多少个使得所有这些连续的子序列都是好的?求计数模数 998244353.

约束

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq 2N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
a_1 \ldots a_{2N}

输出

打印答案。


示例输入 1

3
1 1 2 3 4 5

示例输出 1

2

以下两个分区满足条件。

  • (1,1,2,3,4,5)
  • (1,1,2,3),(4,5)

示例输入 2

1
1 2

示例输出 2

1

示例输入 3

1
1 1

示例输出 3

0

示例输入 4

12
4 2 17 12 18 15 17 4 22 6 9 20 21 16 23 16 13 2 20 15 16 3 7 15

示例输出 4

2048