F - Good Division Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

数列 X が次の条件を満たす時、X を良い数列と呼ぶことにします。

  • 次の操作を 0 回以上繰り返すことで X を空の列に出来る。
    • X の隣り合う 2 要素 x_i,x_{i+1} であって x_i \neq x_{i+1} を満たすものを選び、削除する。

2N 要素の数列 A=(a_1,\ldots,a_{2N}) が与えられます。
A を 1 個以上の連続部分列に分割する方法は 2^{2N-1} 通りありますが、そのうち各連続部分列がすべて良い数列であるようなものが何通りあるかを 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

以下の 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

Score : 900 points

Problem Statement

A sequence X is called good when the following holds.

  • X can be emptied by repeating the following operation zero or more times.
    • Delete two adjacent elements x_i and x_{i+1} of X such that x_i \neq x_{i+1}.

You are given a sequence with 2N elements: A=(a_1,\ldots,a_{2N}).
Among the 2^{2N-1} ways to divide A into one or more contiguous subsequences, how many are such that all those contiguous subsequences are good? Find the count modulo 998244353.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq a_i \leq 2N
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
a_1 \ldots a_{2N}

Output

Print the answer.

Sample Input 1

3
1 1 2 3 4 5

Sample Output 1

2

The following two divisions satisfy the condition.

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

Sample Input 2

1
1 2

Sample Output 2

1

Sample Input 3

1
1 1

Sample Output 3

0

Sample Input 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

Sample Output 4

2048