#446. [AHOI2018初中组]报名签到

[AHOI2018初中组]报名签到

题目描述

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

输入格式

第一行一个整数 nn ,表示报名签到的同学人数。

第二行有 nn 个整数,第 ii 个整数 aia_i 表示第 ii 个同学必须与其他同学保持的距离。

输出格式

输出一行,包括一个整数,表示这 nn 位同学排队队列的最小长度。

注意: nn 位同学要按 11nn 的次序从前往后排队。

3
3 1 2
5

提示

对于 20%20\% 的数据满足:1n201\le n\le 20

对于 70%70\% 的数据满足:1n1041\le n\le 10^4

对于 100%100\% 的数据满足:1n1051\le n\le 10^51ai1051\le a_i\le 10^5