#P11545. [2025年Noi模拟]MEX求和

[2025年Noi模拟]MEX求和

题目描述

对于一个非负整数序列 AA,定义 MEX(A)MEX(A) 为最小的不在 AA 中出现的非负整数。

现在给定非负整数序列 B1,B2,⋯ ,BnB_1,B_2,\cdots,B_n,求所有满足 0≤Ai≤Bi (i=1,⋯ ,n)0\le A_i\le B_i~(i=1,\cdots,n) 的非负整数序列 AA 的 MEX(A)MEX(A) 之和,答案对 109+710^9+7 取模。

输入格式

第一行:一个正整数 nn。

第二行:nn 个整数 B1,B2,⋯ ,BnB_1,B_2,\cdots,B_n。

输出格式

一个整数,表示答案。

样例输入1

5
6 8 3 2 1

样例输出1

2824

样例输入2

8
3 7 1 11 0 4 1 9

样例输出2

208746

数据范围

对于所有数据,满足 1≤n≤50001\le n\le 5000,0≤Bi≤1090\le B_i\le 10^9。

子任务编号 分值 n≤n\le Bi≤B_i\le
1 10 77
2 15 1818 10910^9
3 300300 300300
4 20 10910^9
5 50005000 50005000
6 10910^9