Read problem statements in [Mandarin], [Vietnamese], and [Russian] as well.

Miana and Serdenopis have guests for dinner tonight and thus they have prepared N pairs of slippers for their guests (who shall take off their shoes before entering the house).
The slippers are on a line and the i-th pair of slippers has size S_{i}.

When a guest enters, he takes the first pair of slippers which are still in the line (i.e., they are not taken by a previous guest) and are big enough for him (that is, the slippers' size must be larger or equal than his shoes' size) and does not touch any other pair of slippers. If he cannot find any fitting slippers, he does not take any pair of slippers.

Miana and Serdenopis do not remember how many guests they will have for dinner (and of course, they don't know their shoes' sizes either), but they are interested in the possible subsets of taken slippers.

A (possibly empty) subset of the slippers is interesting if there is a configuration of guests such that all the slippers in the subset are taken and all the slippers not in the subset are not taken.

Count the number of interesting subsets. Since this number may be very large, compute it modulo 998\,244\,353.

------ Input Format ------ 

- The first line contains a single integer N, the number of pairs of slippers.
- The second line contains N integers S_{1},S_{2},\ldots, S_{N}, where the i-th pair of slippers in the line has size S_{i}.

------ Output Format ------ 

Print the number of interesting subsets modulo 998\,244\,353.

------ Constraints ------ 

$1≤N ≤200\,000$
$1≤S_{i}≤200\,000$

----- Sample Input 1 ------ 
3
38 43 41
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 

Explanation of the first testcase: The sizes of the slippers are, in order, $[38, 43, 41]$. 

The $6$ interesting subsets are (the slippers in the interesting subset are given in bold):

$[38, 43, 41]$ (the empty subset is interesting) 
$[\textbf{38}, 43, 41]$ (only the first pair of slippers is taken) 
$[38, \textbf{43}, 41]$ (only the second pair of slippers is taken) 
$[\textbf{38}, \textbf{43}, 41]$ 
$[38, \textbf{43}, \textbf{41}]$
$[\textbf{38}, \textbf{43}, \textbf{41}]$ (all slippers are taken)

Let us describe, for certain configurations of guests, which slippers are taken:

If there is only one guest and his shoes' size is $44$, he will not take any pair of slippers because they are too small for him. The subset of taken slippers is the empty set in this case. 
Assume that there are two guests, the first one has shoes' size $41$ and the second one has shoes' size $42$. The first guest takes the second pair of slippers (with size $43$) and the second guest does not take any pair of slippers because the remaining slippers are too small for him. The subset of taken slippers is $[38, \textbf{43}, 41]$ in this case. 
Assume that there are two guests, the first one has shoes' size $42$ and the second one has shoes' size $41$. The first guest takes the second pair of slippers (with size $43$) and the second guest takes the third pair of slippers (with size $41$). The subset of taken slippers is $[38, \textbf{43}, \textbf{41}]$ in this case. 
Assume that there are $100$ guests, all with shoes' size equal to $36$. The first three guests take, in order, the three available pairs of slippers and the remaining guests take no slippers. The subset of taken slippers is $[\textbf{38}, \textbf{43}, \textbf{41}]$ in this case.

----- Sample Input 2 ------ 
8
42 42 43 37 38 38 41 42
----- Sample Output 2 ------ 
29
----- explanation 2 ------

Difficulty: VERY_HARD
Tags: Constructive algorithms

Range queries

Greedy algorithms

Segment trees revisited

Dynamic programming

Data structures

Ad-hoc
Skill types: Dynamic programming

Data structures

Range queries

Greedy algorithms

Starter code:

Solutions:
c = 200000
mod = 998244353
st = [0] * (4 * c)

def update(idx, ss, se, summ, num):
	if ss == se and ss == num:
		st[idx] = (st[idx] + summ) % mod
		return
	mid = (ss + se) // 2
	if mid >= num:
		update(2 * idx + 1, ss, mid, summ, num)
	else:
		update(2 * idx + 2, mid + 1, se, summ, num)
	st[idx] = (st[idx * 2 + 1] + st[idx * 2 + 2]) % mod

def rangesum(idx, ss, se, rs, re):
	if rs <= ss and se <= re:
		return st[idx]
	elif re < ss or se < rs:
		return 0
	else:
		mid = (ss + se) // 2
		return (rangesum(2 * idx + 1, ss, mid, rs, re) + rangesum(2 * idx + 2, mid + 1, se, rs, re)) % mod
n = int(input())
s = list(map(int, input().split()))
for i in range(n):
	count = 1
	if s[i] != 1:
		count = (1 + rangesum(0, 1, 200000, 1, s[i] - 1)) % mod
	update(0, 1, 200000, count, s[i])
print((st[0] + 1) % mod)


n = int(input())
s = list(map(int, input().split()))
a = sorted(([s[i], -i] for i in range(n)))
index = [-1] * n
for i in range(n):
	index[-a[i][1]] = i
mod = 998244353
size = 1 << n.bit_length() + 1
tree = [0] * (2 * size + 1)
res = 0
for i in range(n):
	small_sum = 0
	j = index[i] + size
	(l, r) = (size, j - 1)
	while l < r:
		if l & 1:
			small_sum = (small_sum + tree[l]) % mod
			l += 1
		if r & 1 == 0:
			small_sum = (small_sum + tree[r]) % mod
			r -= 1
		l //= 2
		r //= 2
	small_sum = (small_sum + tree[l]) % mod
	res = (res + small_sum + 1) % mod
	tree[j] = (small_sum + 1) % mod
	while j // 2 > 0:
		j //= 2
		tree[j] = (tree[j * 2] + tree[j * 2 + 1]) % mod
print((res + 1) % mod)


MOD = 998244353
MAX = 1000010
sz = 400000
bTree = []

def summ(index):
	sum = 0
	index += 1
	while index > 0:
		sum += bTree[index]
		sum %= MOD
		index -= index & -index
	return sum % MOD

def updateBit(n, idx, v):
	idx += 1
	while idx <= n:
		bTree[idx] += v
		bTree[idx] %= MOD
		idx += idx & -idx
n = int(input())
s = list(map(int, input().split()))
bTree = [0 for _ in range(MAX)]
for i in range(n):
	updateBit(sz, s[i], summ(s[i] - 1) + 1)
print((summ(sz) + 1) % MOD)


import os
import sys
import math
import operator
from random import randint, randrange
from collections import defaultdict, Counter, deque
from itertools import count, permutations, combinations
from itertools import groupby, accumulate
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = 998244353
PROFILE = False
MAX = 1000010
sz = 400000
bTree = []

def summ(index):
	sum = 0
	index += 1
	while index > 0:
		sum += bTree[index]
		sum %= MOD
		index -= index & -index
	return sum % MOD

def updateBit(n, idx, v):
	idx += 1
	while idx <= n:
		bTree[idx] += v
		bTree[idx] %= MOD
		idx += idx & -idx
n = int(input())
s = list(map(int, input().split()))
bTree = [0 for _ in range(MAX)]
for i in range(n):
	updateBit(sz, s[i], summ(s[i] - 1) + 1)
print((summ(sz) + 1) % MOD)