← 返回题目列表

Codeforces · 1696/E

E. 放置吉纳斯

中文机器翻译题面 查看原题

我们说无限序列 $$$a_{0}, a_{1}, a_2, \ldots$$$ 是非增的当且仅当对于所有 $$$i\ge 0$$$, $$$a_i \ge a_{i+1}$$$。

有一个无限的右下网格。左上角单元格的坐标为 $$$(0,0)$$$。行从上到下编号为 $$$0$$$ 到无穷大,列从左到右编号为 $$$0$$$ 到无穷大。

还有一个非增无限序列 $$$a_{0}, a_{1}, a_2, \ldots$$$。您将获得 $$$a_0$$$、$$$a_1$$$、$$$\ldots$$$、$$$a_n$$$;对于所有$$$i>n$$$,$$$a_i=0$$$。对于每对 $$$x$$$、$$$y$$$,如果 $$$y<a_x$$$,则坐标为 $$$(x,y)$$$ 的单元格(位于 $$$x$$$ 行和 $$$y$$$ 列的交叉点)为白色,否则为黑色。

最初,$$$(0,0)$$$ 上有一个名为 Jina 的玩偶。您可以进行以下操作。

- 在 $$$(x,y)$$$ 上选择一个娃娃。将其取下并在 $$$(x,y+1)$$$ 上放置一个娃娃,然后在 $$$(x+1,y)$$$ 上放置一个娃娃。

请注意,一个牢房中可以同时出现多个玩偶;在一项操作中,您仅删除一项。您的目标是让所有白色单元格都包含 $$$0$$$ 娃娃。

实现目标所需的最少操作次数是多少?打印以 $$$10^9+7$$$ 为模的答案。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$)。

输入的第二行包含 $$$n+1$$$ 整数 $$$a_0,a_1,\ldots,a_n$$$ ($$$0\le a_i\le 2\cdot 10^5$$$)。

保证序列 $$$a$$$ 是非递增的。

输出

打印一个整数 — 问题的答案,以 $$$10^9+7$$$ 为模。

示例

输入 #1

2
2 2 0

输出 #1

5

输入 #2

10
12 11 8 8 6 6 6 5 3 2 1

输出 #2

2596

注意

考虑第一个例子。在给定的网格中,单元格 $$$(0,0),(0,1),(1,0),(1,1)$$$ 为白色,所有其他单元格为黑色。让我们用三元组来描述网格:三元组$$$(x,y,z)$$$表示单元格$$$(x,y)$$$上放置了$$$z$$$玩偶。最初网格的状态是$$$(0,0,1)$$$。

最佳操作顺序之一如下:

- 使用 $$$(0,0)$$$ 进行运算。现在网格的状态是$$$(1,0,1),(0,1,1)$$$。
- 使用 $$$(0,1)$$$ 进行运算。现在网格的状态是$$$(1,0,1),(1,1,1),(0,2,1)$$$。
- 使用 $$$(1,0)$$$ 进行运算。现在网格的状态是$$$(1,1,2),(0,2,1),(2,0,1)$$$。
- 使用 $$$(1,1)$$$ 进行运算。现在网格的状态是$$$(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$$$。
- 使用 $$$(1,1)$$$ 进行运算。现在网格的状态是$$$(0,2,1),(2,0,1),(1,2,2),(2,1,2)$$$。

现在所有白色单元格都包含$$$0$$$娃娃,所以我们通过$$$5$$$操作达到了目标。