Help Prapor
Prapor is not in the mood for jokes, he decided to take part in the contest. Just help him solve the problem. Consider an array a of n numbers, where n is odd. Let's build a complete weighted graph, that will have n + 1 vertices. The weight of the edge between vertices u and v (1 ≤ u < v ≤ n) is equal to the maximum from a[u], a[u+1], ..., a[v-1]. The cost of the array a is the maximum weight of an ideal matching in the constructed graph. An ideal matching is a matching that covers all vertices.
You are given an array a consisting of n distinct integers. Calculate the sum of the costs of all permutations of the array a modulo 998 244 353.
Input
The first line contains one odd integer n (1 ≤ n ≤ 10^5) - the length of the array a. The second line contains n distinct integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^8).
Output
Print a single number - the sum of the costs of all permutations of the array a modulo 998 244 353.