/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A = (A_1, A_2, \dots, A_N) が与えられます。
A の連続するとは限らない、長さが 2 以上である部分列 A'=(A'_1,A'_2,\ldots,A'_k) のうち以下の条件を満たすものの個数を求めてください。
- A'_1 \leq A'_k
なお、この値は非常に大きくなることがあるため、998244353 で割ったあまりを出力してください。
ただし、2 つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の連続するとは限らない、長さが 2 以上である部分列のうち問題文中の条件を満たすものの個数を、998244353 で割ったあまりを出力せよ。
入力例 1
3 1 2 1
出力例 1
3
A=(1,2,1) の連続するとは限らない、長さが 2 以上である部分列は (1,2), (1,1), (2,1), (1,2,1) の 4 通りあります。
そのうち問題文中の条件を満たすものは、(1,2), (1,1), (1,2,1) の 3 通りです。
入力例 2
3 1 2 2
出力例 2
4
列として同じであっても、取り出す添字が異なる場合 2 つの部分列は区別されることに注意してください。
この入出力例において、問題文中の条件を満たすような部分列は (1,2), (1,2), (2,2), (1,2,2) の 4 通りです。
入力例 3
3 3 2 1
出力例 3
0
問題文中の条件を満たすような部分列が存在しない場合もあります。
入力例 4
10 198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
出力例 4
830
Score : 500 points
Problem Statement
Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).
Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:
- A'_1 \leq A'_k.
Since the count can be enormous, print it modulo 998244353.
Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the condition in Problem Statement.
Sample Input 1
3 1 2 1
Sample Output 1
3
A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).
Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.
Sample Input 2
3 1 2 2
Sample Output 2
4
Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.
In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.
Sample Input 3
3 3 2 1
Sample Output 3
0
There may be no subsequence that satisfies the condition.
Sample Input 4
10 198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
Sample Output 4
830