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 au, au+1, ..., av-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 ≤ 105) - the length of the array a. The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 108).

Output

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