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.

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.

Constraints

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

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

见题面 Input 部分

见题面 Output 部分