X学校的机房

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

X学校有一个机房,有一天,因为N同学的误操作,机房中了病毒,学校种种原因一个月没有管,然后病毒疯狂变异,生成了很多种病毒不规则的分布在1-n号服务器中,我们的G同学觉得这样不行,他就编写了一个特别强大的杀毒软件,它每次运行可以删除从p号到q号所有服务器的任意一种病毒(p-q号服务器中每一台都至少要有任意一种病毒,若有其中一台没有,这个杀毒软件就会认为杀毒结束而中断),G同学觉得无脑循环杀毒软件过于无脑,不符合G同学大佬的身份,所以他一定要用最少的次数杀完毒,所以他又编写一个特别强大的扫描软件,扫描出了这n台服务器每台服务器有多少病毒,现在只差最后一步编写杀毒方法的程序了,这时,G同学发现在旁边同属实验室的你,他觉得就他一个人干活不行,所以让你编写这个求杀毒方法的程序,并且他觉得你们不行,所以只要求你算出最少要运行多少次这个杀毒软件。因为结果过大,请输出次数对100000取余的结果。
事后,G同学:" ??? "

输入格式

输入文件为两行,第一行为一个数字n。第二行是n个数字代表1-n台服务器内的病毒数。

输出格式

输出文件为一行一个整数,代表杀毒软件最少运行次数对100000取余的结果。

样例

输入样例

6
1 2 3 2 4 6

输出样例

7

样例说明

第一次:删除1-6, 变为0 1 2 1 3 5
第二次:删除2-6, 变为0 0 1 0 2 4
第三次:删除3-3, 变为0 0 0 0 2 4
第四次:删除5-6, 变为0 0 0 0 1 3
第五次:删除5-6, 变为0 0 0 0 0 2
第六次:删除6-6, 变为0 0 0 0 0 1
第七次:删除6-6, 变为0 0 0 0 0 0

数据规模

30%数据 n<=10^4
70%数据 n<=10^5
100%数据 n<10^6病毒数<=10^6

2019XJU软件实验室大一考核

未参加
状态
已结束
规则
OI
题目
6
开始于
2019-11-23 11:00
结束于
2019-11-23 13:30
持续时间
2.5 小时
主持人
参赛人数
31