프라포르를 도와주세요

프라포르는 농담할 기분이 아니지만, 대회에 참가하기로 했다. 그가 이 문제를 풀 수 있도록 도와주세요.

$n$이 홀수인 길이 $n$의 배열 $a$를 생각합시다. 정점이 $n + 1$개인 완전 가중 그래프를 만듭니다. 정점 $u$와 $v$ ($1 \le u < v \le n$)를 잇는 간선의 가중치는 $a_u, a_{u+1}, \dots, a_{v-1}$ 중 최댓값입니다. 배열 $a$의 비용은 이 그래프에서 가능한 완전 매칭의 가중치 합 중 최댓값으로 정의합니다. 완전 매칭은 모든 정점을 덮는 매칭입니다.

서로 다른 정수 $n$개로 이루어진 배열 $a$가 주어집니다. $a$의 모든 순열에 대한 비용의 총합을 구하고, 그 값을 $998\,244\,353$으로 나눈 나머지를 출력하세요.

첫째 줄에 배열 $a$의 길이인 홀수 정수 $n$이 주어진다 ($1 \le n \le 100\,000$). 둘째 줄에는 서로 다른 정수 $a_1, a_2, \dots, a_n$이 주어진다 ($1 \le a_i \le 10^8$).

$a$의 모든 순열에 대한 비용의 총합을 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.