eolymp
bolt
Try our new interface for solving problems
Problems

Help Prapor

Help Prapor

Time limit 1 second
Memory limit 128 MiB

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 (1u < vn) 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 data

The first line contains one odd integer n (1n10^5) - the length of the array a. The second line contains n distinct integers a[1], a[2], ..., a[n] (1a[i]10^8).

Output data

Print a single number - the sum of the costs of all permutations of the array a modulo 998 244 353.

Examples

Input example #1
3
1 30 15
Output example #1
300
Source 2020 Cycle of Internet Olympiads for schoolchildren, Fifth team contest, Novemver 28, Advanced level, Problem D