logo AlgoBeat OnlineJudge
登录 注册

#215174. [UOI 2021 II Stage] 奇迹之地

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

最近,哥萨克胡子听说了一个有趣的地方,叫做奇迹之地,那里生长着结满金钱的树木。他决定种下 棵钱树,并在第二年收获。

当胡子回到奇迹之地视察时,他发现每棵树上至少长出了一枚硬币,并且第 棵树上的硬币数量为 。他觉得亲自收获太费时间,于是制造了一台机器,这台机器可以多次执行以下操作:

  • 选择一个正整数
  • 找到当前硬币数至少为 的第一棵树(即索引最小的树);
  • 从该树上取走 枚硬币。

但在钱树养护手册中,哥萨克胡子了解到,收获后每棵树上必须至少留下一枚硬币,否则它们明年将不会结果。

现在哥萨克胡子想知道,经过若干次操作后,这台机器最多能收获多少硬币。

请注意,不同操作中选择的数字 可以不同。

输入格式

第一行包含一个整数 () —— 奇迹之地上的树的数量。

第二行包含 个整数 () —— 树上硬币的初始数量。

输出格式

输出一个整数 —— 机器经过一系列操作后最多能收集到的硬币数量,同时确保每棵树上至少留下一枚硬币。

样例

样例输入 1

4
1 4 2 3

样例输出 1

3

样例输入 2

6
1 2 2 3 4 2

样例输出 2

0

数据范围与提示

样例说明

在第二个样例中,无法选择一个 使得能收集到至少一枚硬币,同时还能在每个树上都留下硬币。

评分细则

  • (4 分):
  • (8 分):
  • (7 分):
  • (13 分):
  • (7 分):
  • (19 分):
  • (42 分): 无额外限制。

翻译由 DeepSeek V3 完成