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

题目描述

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