레이저 타워 - 题目

수평선 위의 $x=1,2,\ldots,N$에 각각 타워가 하나씩 있다. 위치가 $x=i$인 타워의 높이는 $h_i$이며, $h_1,h_2,\ldots,h_N$은 $1$부터 $N$까지의 정수로 이루어진 순열이다.

각 타워의 꼭대기인 $(i,h_i)$에서 레이저를 반반의 확률로 왼쪽 또는 오른쪽으로 발사한다.

모든 타워의 레이저 발사 방향은 상호 독립적으로 결정된다.

모든 타워에서 레이저를 발사했을 때 덮인 영역들의 합집합의 넓이를 $S$라고 하자. $2^S$의 기댓값을 $998\,244\,353$으로 나눈 나머지를 구하여라.

입력

첫째 줄에 타워의 개수 $N$이 주어진다. ($2 \le N \le 200\,000$)

둘째 줄에 각 타워의 높이를 의미하는 $N$개의 정수 $h_1,h_2,\ldots,h_N$이 공백으로 구분되어 주어진다. 주어지는 높이는 $1$부터 $N$까지의 정수가 한 번씩 등장하는 순열이다.

$2^S$의 기댓값을 $998\,244\,353$으로 나눈 나머지를 출력한다. $998\,244\,353$은 소수이다.

구체적으로, 기댓값은 항상 유리수임이 보장되며, 이를 기약분수 $P/Q$로 나타내었을 때 $Q \not\equiv 0 \pmod{998\,244\,353}$임을 보일 수 있다. 이때,

$$ P \times Q^{-1} \pmod{998\,244\,353} $$

의 값을 출력해야 한다.

입력

2
1 2

출력

입력

3
1 2 3

출력

입력

6
6 5 2 3 4 1

출력

448265500

예제 1에서 전체 공간의 범위는 $x=0$부터 $x=3$까지이다. 1번 타워와 2번 타워가 레이저를 쏘는 4가지 방향 조합에 대해, 덮인 영역들의 합집합의 넓이 $S$와 $2^S$의 값은 다음과 같다. 각각의 상황은 $1/4$의 확률로 일어난다.

왼쪽, 왼쪽: $0 \le x \le 2$ 구간이 높이 $2$로 덮인다. ($S=4$, $2^S=16$)
왼쪽, 오른쪽: $0 \le x \le 1$은 높이 $1$, $2 \le x \le 3$은 높이 $2$로 덮인다. ($S=3$, $2^S=8$)
오른쪽, 왼쪽: $0 \le x \le 2$는 높이 $2$, $2 \le x \le 3$은 높이 $1$로 덮인다. ($S=5$, $2^S=32$)
오른쪽, 오른쪽: $1 \le x \le 2$는 높이 $1$, $2 \le x \le 3$은 높이 $2$로 덮인다. ($S=3$, $2^S=8$)

따라서 $2^S$의 기댓값은

$$ \frac{16+8+32+8}{4}=16 $$

이다.