Not Equal

题目描述

给出一个长度为 $N$ 的整数序列 $C$。求满足以下所有条件的长度为 $N$ 的整数序列 $A$ 的个数。

$1 \leq A_i \leq C_i\, (1 \leq i \leq N)$ A_i \neq A_j\, (1 \leq i < j \leq N)

由于计数可能非常大，请对 $(10^9+7)$ 取模后输出。

输入格式

输入按下述格式从标准输入给出： $N$ $C_1$ $C_2$ $\ldots$ $C_N$

输出格式

输出满足所有条件的序列 $A$ 的数量，对 $(10^9+7)$ 取模。

2
1 3

2

4
3 3 4 4

12

2
1 1

0

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

405924645

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq C_i \leq 10^9$ 输入中的所有数值均为整数。我们有两个满足所有条件的序列 $A$：$(1,2)$ 和 $(1,3)$。
另一方面，例如 $A=(1,1)$ 不满足第二个条件。
没有满足所有条件的序列 $A$，所以我们应当输出 $0$。
注意对 $(10^9+7)$ 取模后输出计数。

标签: AtCoder|abc209C

来源

AtCoder|abc209C