题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 Romanian Master of Informatics 2018 Day2 T3 「W」

一个数字数组如果满足以下条件，就被称为 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$ 取模。

5
3 1 4 2 3

6

7
1 2 2 2 3 4 4

72

提示

样例 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$	无附加限制