길이가 $N$인 수열 $A = (A_1, A_2, \dots, A_N)$이 주어집니다. 이 수열 $A$에 대해 $i = 1, 2, \dots, N - 1$의 순서대로 다음 연산을 수행합니다:
- $A_i$와 $A_{i+1}$을 교환하거나, 아무것도 하지 않습니다.
이 연산들을 수행한 후 만들어질 수 있는 서로 다른 수열의 개수를 $998244353$으로 나눈 나머지를 구하세요.
입력
입력은 다음 형식으로 주어집니다:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- 모든 입력은 정수입니다.
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
출력
정답을 한 줄에 출력합니다.
예제
예제 입력 1
5 1 2 1 2 3
예제 출력 1
10
예제 입력 2
9 3 1 6 2 2 7 7 6 6
예제 출력 2
104
노트
첫 번째 예제에서는 연산을 수행한 후 결과로 나올 수 있는 수열이 $10$가지 있습니다. 이 수열들은 다음과 같습니다:
- $(1, 2, 1, 2, 3)$,
- $(1, 2, 1, 3, 2)$,
- $(1, 2, 2, 1, 3)$,
- $(1, 2, 2, 3, 1)$,
- $(1, 1, 2, 2, 3)$,
- $(1, 1, 2, 3, 2)$,
- $(2, 1, 1, 2, 3)$,
- $(2, 1, 1, 3, 2)$,
- $(2, 1, 2, 1, 3)$,
- $(2, 1, 2, 3, 1)$.