P14534 [RMI 2018] W

翻译来自于 [LibreOJ](https://loj.ac/p/5129)。

**题目译自 [Romanian Master of Informatics 2018](https://rmi.lbi.ro/rmi_2018/) Day2 T3 「[W](https://rmi.lbi.ro/rmi_2018/_dwl/public.zip)」** 一个数字数组如果满足以下条件，就被称为 W 形数组： 1. 它由四个段组成，依次为：递减、递增、递减、递增。 2. 排序非严格，即递增和递减段可能包含连续的相等元素。 3. 每两个连续段共享一个公共端点。 4. 每个段至少包含两个不同值。 例如，数组 $(3, 1, 2, 1, 1, 4)$ 是 W 形的，分为段 $(3, 1)$、$(1, 2)$、$(2, 1, 1)$、$(1, 4)$。而数组 $(3, 1, 2, 2, 2, 4)$ 不是 W 形的，因为虽然可以分为 $(3, 1)$、$(1, 2)$、$(2, 2, 2)$、$(2, 4)$，但段 $(2, 2, 2)$ 不包含两个不同值。 给定一个包含 $N$ 个整数的数组，你需要计算有多少个不同的 W 形排列？两个排列 $(p_1, p_2, \ldots, p_N)$ 和 $(q_1, q_2, \ldots, q_N)$ 若存在某个位置 $1 \leq i \leq N$ 使得 $p_i \neq q_i$，则视为不同。在上述例子中，$(3, 1, 2, 1, 1, 4)$ 只计数一次，因为三个 $1$ 的内部排列不产生不同的排列。

第一行包含一个整数 $N$。第二行包含 $N$ 个空格分隔的整数，表示数组的值。

输出一个整数，表示不同的 W 形排列数量，对 $1000000007$ 取模。

### 样例 1 解释 在第一个样例中，输入数组为 $(3, 1, 4, 2, 3)$，共有 $6$ 个不同的 W 形排列： - $(3, 1, 3, 2, 4)$ - $(3, 1, 4, 2, 3)$ - $(3, 2, 3, 1, 4)$ - $(3, 2, 4, 1, 3)$ - $(4, 1, 3, 2, 3)$ - $(4, 2, 3, 1, 3)$ ### 数据范围 对于所有输入数据，满足： - $5 \leq N \leq 300000$ - 数组值是介于 $[1, 1000000]$ 之间的整数 每个测试点将单独评分。 | 子任务 | 分值 | 附加限制 | | :----: | :----: | :-------: | | $1$ | $20$ | $N$ 个元素中只有两种不同值 | | $2$ | $30$ | $N$ 个元素的值互不相同 | | $3$ | $50$ | 无附加限制 |