/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
長さ k の数列 a=(a_1,a_2,\dots,a_k) が 門松的 であることを、以下のようにして定めます。
- 2 \le i \le k-1 かつ a_{i-1} < a_i かつ a_i > a_{i+1} を満たす整数 i の個数を x とする。
- 2 \le i \le k-1 かつ a_{i-1} > a_i かつ a_i < a_{i+1} を満たす整数 i の個数を y とする。
- x > y であるとき、またそのときに限り、数列 a を 門松的 であると言います。
(1,2,\dots,N) の順列 P が与えられます。
P の (連続でなくともよい) 部分列であって、門松的であるものの個数を 998244353 で割った余りを求めてください。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- P は (1,2,\dots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \dots P_N
出力
答えを出力せよ。
入力例 1
4 1 3 4 2
出力例 1
4
P の部分列のうち、門松的であるものは以下の 4 つです。
- (1,3,4,2)
- (1,3,2)
- (1,4,2)
- (3,4,2)
入力例 2
1 1
出力例 2
0
入力例 3
20 11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3
出力例 3
431610
例えば、部分列 a=(10,13,12,5,7,9,20,3) は門松的です。
- i=2,7 に対して a_{i-1} < a_i かつ a_i > a_{i+1} が成り立つので、 x=2 です。
- i=4 に対して a_{i-1} > a_i かつ a_i < a_{i+1} が成り立つので、 y=1 です。
- x > y であるので、部分列 a は門松的です。
Score : 525 points
Problem Statement
A sequence a=(a_1,a_2,\dots,a_k) of length k is defined to be kadomatsu-like as follows:
- Let x be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} < a_i, and a_i > a_{i+1}.
- Let y be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} > a_i, and a_i < a_{i+1}.
- The sequence a is called kadomatsu-like if and only if x > y.
You are given a permutation P of (1,2,\dots,N).
Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of P that are kadomatsu-like.
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- P is a permutation of (1,2,\dots,N).
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N
Output
Output the answer.
Sample Input 1
4 1 3 4 2
Sample Output 1
4
Among the subsequences of P, the following four are kadomatsu-like:
- (1,3,4,2)
- (1,3,2)
- (1,4,2)
- (3,4,2)
Sample Input 2
1 1
Sample Output 2
0
Sample Input 3
20 11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3
Sample Output 3
431610
For example, the subsequence a=(10,13,12,5,7,9,20,3) is kadomatsu-like.
- We have a_{i-1} < a_i and a_i > a_{i+1} for i=2,7, so x=2.
- We have a_{i-1} > a_i and a_i < a_{i+1} for i=4, so y=1.
- Since x > y, the subsequence a is kadomatsu-like.