더 좁은 통로

당신은 ICPC 왕국의 전략가입니다. 왕국 근처의 좁은 통로가 몬스터의 공격을 받을 것이라는 정보를 입수했습니다. 통로는 $2$개의 행($1$부터 $2$까지 번호가 매겨짐)과 $N$개의 열($1$부터 $N$까지 번호가 매겨짐)로 이루어진 격자입니다. $(r, c)$는 $r$행 $c$열의 칸을 뜻합니다. 매일 힘이 $P_{r,c}$인 병사 한 명이 $(r, c)$를 지키도록 배치됩니다.

통로에는 안개가 매우 자주 낍니다. 하루 동안 각 열은 $50\%$의 확률로 안개에 덮입니다. 열이 안개에 덮이면, 그 열에 배치된 병사 두 명은 그날 출동하지 않습니다. 그렇지 않으면 배치된 병사들이 출동합니다.

연결 구간 $[u, v]$ ($u \le v$)는 $u$열부터 $v$열까지 연속된 열들의 극대 집합으로, 집합에 속한 어떤 열도 안개에 덮이지 않은 구간입니다. 아래 그림은 예시입니다. 회색 칸은 안개에 덮인 칸입니다. 연결 구간은 $4$개이며, 각각 $[1, 2]$, $[4, 6]$, $[9, 9]$, $[11, 11]$입니다.

연결 구간 $[u, v]$의 강도는 다음과 같이 계산합니다. $m_1$과 $m_2$를 해당 연결 구간에서 1행과 2행 병사들의 최대 힘이라고 합시다. 식으로 쓰면 $r \in \{1, 2\}$에 대해 $m_r = \max(P_{r,u}, P_{r,u+1}, \dots, P_{r,v})$입니다. $m_1 = m_2$이면 강도는 $0$입니다. 그렇지 않으면 강도는 $\min(m_1, m_2)$입니다.

배치의 총 강도는 모든 연결 구간 강도의 합입니다. 하루 동안 배치의 총 강도의 기댓값을 구하세요.

첫 번째 줄에 정수 $N$ ($1 \le N \le 100\,000$)이 주어집니다.

다음 두 줄에는 각각 $N$개의 정수 $P_{r,c}$ ($1 \le P_{r,c} \le 200\,000$)가 주어집니다.

$M = 998\,244\,353$이라고 합시다. 총 강도의 기댓값은 기약분수 $\frac{x}{y}$로 나타낼 수 있음이 알려져 있습니다. 여기서 $x$와 $y$는 정수이며 $y \not\equiv 0 \pmod M$입니다. $0 \le k < M$이고 $k \cdot y \equiv x \pmod M$을 만족하는 정수 $k$를 한 줄에 출력하세요.