问题 3914 --1.报名签到(signin)

3914: 1.报名签到(signin)

题目描述

  n 位同学(编号从 1 到 n)同时来到体育馆报名签到,领取准考证和参赛资料。为了有序报名,这 n 位同学需要按编号次序(编号为 1 的同学站在最前面)从前往后排成一条直线。然而每一位同学都不喜欢拥挤,对于第 i 位同学,如果有另外一位同学距离他(她)的距离小于 a[i],那么就会发生冲突。小可可想知道如果要不发生任何冲突的情况下,这 n 位同学排队的队列最短长度是多少。

输入

输入有两行:
第一行一个整数 n,表示报名签到的同学人数。
第二行有 n 个整数,第 i 个整数 a[i]表示第 i 个同学必须与其他同学保持的距离。

输出

输出一行,包括一个整数,表示这 n 位同学排队队列的最小长度。
注意:n 位同学要按 1~n 的次序从前往后排队。

样例输入输出

输入#1 复制
3
3 1 2
输出#1 复制
5

提示

【数据范围】
对于 20%的数据满足:1≤n≤20;
对于 70%的数据满足:1≤n≤10000;
对于 100%的数据满足:1≤n≤100000,1≤a[i]≤100000。

序号 标题 作者 发表时间 费用 订购数 操作