You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

什么是Peak序列呢？如果一个序列中的数按照先非严格递增，再非严格递减的顺序排列，那么我们称这个序列为Peak序列。例如 1，3，3，5，5，2 就是一个Peak序列，它满足如上条件，而5，2，5，5，3，3，1 和1，3，3，5，2，5均不是Peak序列，同理 1，3，3，5，5 和5，5，3，2 均是Peak序列。

题目描述

现在给你一个含有n个数的序列，希望你能计算出由这个序列重新排序以后，可以组成多少种不同的Peak序列，结果对998244353取模。

输入

共两行

一行为$n$，表示给定的序列长度。

第二行为$n$个数$a_i$，表示给定的序列。

输出

一个数，表示对998244353取模后的答案。

样例

3
3 2 2

3

样例解释

排列后的Peak序列有 3，2，2 和 2，3，2 和2，2，3，共3种，3%998244353=3，所以答案为3。

数据范围

• $1\le n \le 1\times 10^6$

• $1\le a_i \le 1 \times 10^5$