애플 가족 재회

배경

비 오는 밤, 후드를 쓴 암말 한 마리가 텅 빈 시장에 뛰어들어 어두운 골동품 가게로 들어간다. 그녀는 작은 촛불이 켜질 때까지 가게 안을 뒤진다.

"어서 오세요, 여행자님. 무엇을 도와드릴까요?" 가게 주인인 수말이 나와서 묻는다. 카운터 뒤로 들어간 그는 이 손님을 가게로 이끈 것이 무언가 강력한 물건일 거라고 짐작한다. 그녀는 그의 뒤편 선반에서 유리 상자에 담겨 있는, 진홍색 보석이 박힌 護符를 가리킨다.

"아, 안목이 높으시군요. 알리콘 부적은 알려진 마법 부적 가운데 가장 신비롭고 강력한 것 중 하나입니다. 어, 아... 아무래도 이건 너무 위험합니다."

(암말이 금화가 든 큰 주머니를 카운터 위에 던진다.)

"포장해 드릴까요?"

$\ldots$

다음 날 아침, 모든 포니가 깨어나 보니 자신이 순열로 바뀌어 있다!

에쿠스트리아에는 $n!$마리의 포니가 있다. 사악한 마법이 모든 포니를 길이 $n$인 서로 다른 순열 $n!$개 가운데 하나로 바꿔 놓았다.

패닉을 줄이기 위해, 순열 $A$로 바뀐 애플잭은 가능한 한 빨리 가족을 모으기로 한다. 그녀는 다른 순열 $P$에 대해, 1-2-3 변환을 여러 번 적용해서 자신을 $P$로 바꿀 수 있다면 $P$가 애플 가족에 속한다는 것을 알아챈다.

1-2-3 변환은 다음과 같다. 인접한 원소 세 개 $A_i, A_{i+1}, A_{i+2}$를 고른다. $A_i$가 이 세 수의 중앙값이면, 이것을 $A_{i+2}$ 뒤로 보낼 수 있다. 즉 세 원소를 $A_{i+1}, A_{i+2}, A_i$로 바꾼다. $A_{i+2}$가 세 수의 중앙값이면, 이것을 $A_i$ 앞으로 보낼 수 있다. 즉 세 원소를 $A_{i+2}, A_i, A_{i+1}$로 바꾼다.

한 순열을 1-2-3 변환으로 다른 순열로 바꿀 수 있다면, 두 순열은 같은 가족에 속한다. 각 가족에서 사전순으로 가장 작은 순열을 그 가족의 대표로 고른다. 가족들을 대표 순열의 사전순으로 정렬하면 가족 목록 $F_1, F_2, \ldots$을 얻는다. 예를 들어 $(1, 2, \ldots, n)$은 항상 $F_1$에 속한다.

각 포니는 자기 가족의 임시 대피소로 가야 한다. $P \in F_i$이면 포니 $P$는 가족을 만나기 위해 대피소 $i$로 가야 한다.

애플잭이 애플 가족이 가야 할 대피소 번호와 가족에 속한 포니 수를 찾도록 도와주세요.

첫 줄에 정수 $n$ ($3 \le n \le 10^5$)이 주어진다. 둘째 줄에는 애플잭이 바뀐 순열 $A$를 나타내는 정수 $A_1, A_2, \ldots, A_n$이 주어진다.

정수 하나를 한 줄에 출력한다. $A \in F_i$를 만족하는 유일한 $i$가 존재한다. $i \leq 65{,}472$이면 애플 가족에 속한 포니 수를 $998{,}244{,}353$으로 나눈 나머지를 출력한다. 그렇지 않으면 $i$를 $998{,}244{,}353$으로 나눈 나머지를 출력한다.

가족은 모두 4개다.

• $F_1 = \{(1, 2, 3)\}$
• $F_2 = \{(1, 3, 2), (2, 1, 3)\}$
• $F_3 = \{(2, 3, 1), (3, 1, 2)\}$
• $F_4 = \{(3, 2, 1)\}$

따라서 애플 가족은 $F_2 = \{(1, 3, 2), (2, 1, 3)\}$이고, 대표는 $(1, 3, 2)$이다. 그러므로 애플 가족에 속한 포니 수인 2를 출력한다.