#4798. [Ceoi2015]Calvinball championship

题目描述

有n个人参加一场比赛，需要把他们分成若干组，然后就会给他们每人一个编号。

编号发放的规则：

1：每个组的队长为组员中名字字典序最小的那个人

2：每个组的编号为这个组的队长名字的排名（按字典序，且只有队长参与排名）

3：每个人的编号即为他所在组的编号

然后将所有人按字典序排好，根据他们的编号就可以产生一个序列。

例如：

有6个人，分为3组

（Calvin，Hobbes，Susie），（Batman），（Jerry ，Tom） 下划线的是队长

（Batman）为第一组，（Calvin，Hobbes，Susie）为第二组，（Jerry ，Tom）为第三组

所以6人编号分别为Batman 1 ，Calvin 2，Hobbes 2，Susie 2，Jerry 3，Tom 3。

再将6人名字排序，有

Batman 1

Calvin 2

Hobbes 2

Jerry 3

Susie 2

Tom 3

所以序列为1 2 2 3 2 3。

现在给出一个序列，求它按照字典序是第多少大的，答案mod 1000007。（具体意思见样例解释）

输入格式

第一行一个n代表有多少个人参赛

接下来一行n个数，代表序列

n<=10000，保证给出的序列是存在的

输出格式

输出这个序列是第几大的，mod 1000007。

样例

样例输入

3  

1 2 2

样例输出

4  

样例解释  

有三个人，假设他们叫A、B、C  

当为（A，B，C）时，序列为 1 1 1  

当为（A，B），（C）时，序列为1 1 2  

当为（A，C），（B）时，序列为1 2 1  

当为（A），（B，C）时，序列为1 2 2  

当为（A），（B），（C）时，序列为1 2 3.  

所以，1 2 2是第4大的  

数据范围与提示