3993. 傲娇

单点时限: 1.0 sec

内存限制: 512 MB

Little Fang 是个矛盾的人。

她既喜欢相同,又喜欢不相同;她既想要嵌套,又想要平铺;她既想要最大,又想要最小。于是她找到 Cuber QQ,向 Cuber QQ 倾诉她的心情。Cuber QQ 看到 Little Fang 一副“看破红尘”的矫揉造作之态,感到非常的 ***。

为了让 Little Fang 别来烦自己,也满足 Little Fang 奇怪的癖好,Cuber QQ 送给了 Little Fang 一些东西。

他给了一个序列 $a_1,a_2,\ldots,a_n$ 和一个排列 $p_1,p_2,\ldots,p_n$;$a$ 中可能有 相同 的数,而 $p$ 中的数互 不相同

他给了 $a$ 的一个排列 $a’=( a_{p_1},a_{p_2},\ldots,a_{p_n} )$;$a_{p_i}$ 是 嵌套 的,而 $a’_1,a’_2\ldots,a’_n$ 是 平铺 的。

他给了一个 最小 值函数 $w(l,r)=\min_{l\le i\le r}a’_i$。

收到礼物的 Little Fang 是又惊喜又不悦。她感受到了 Cuber QQ 浓浓的关心,但她发现 Cuber QQ 漏掉了「最大」这一属性,这不由得让 Little Fang 认为,这是 Cuber QQ 故意在表达不满。不过,善解人意的 Little Fang 并没有去找 Cuber QQ 理论,而是依靠自己补满了空缺:她定义了 Cuber QQ 礼物带给他的满意度:$F=\sum_{1\le l\le r\le n}w(l,r)$。

Little Fang 希望算出,有多少个排列 $p_1,\ldots,p_n$ 使得 $F$ 最大。她将用这个问题的答案来向 Cuber QQ 表达歉意。

由于 Little Fang 比较傲娇,所以她不会在 Cuber QQ 的面前演算这道题。她希望你帮他算出答案,并对 $10^9+7$ 取模。

输入格式

第一行一个数 $n$($1\le n\le 5\cdot 10^5$)。

接下来一行 $n$ 个数表示 $a_1,a_2,\ldots,a_n$($1\le a_i\le 10^9$)。

输出格式

输出一行表示排列 $p$ 的个数。

样例

Input
5
1 1 1 1 1
Output
120

57 人解决,68 人已尝试。

61 份提交通过,共有 258 份提交。

3.9 EMB 奖励。

创建: 11 月,1 周前.

修改: 11 月,1 周前.

最后提交: 3 周前.

来源: EOJ Monthly 2020.11

题目标签