## Larry's Array

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

Let's define a special array of length as an array where the first occurrence of comes before the first occurence of for all , where is the maximum element of the array. A special array is considered better than a special array if is lexicographically less than .

Everyone at Larry's school is collecting special arrays of length these days. Being very competitive, Larry wants to know how many special arrays of length are at least as good as his modulo . Can you help him?

#### Input Specification

The first line will contain one integer .

The second line will contain integers . It is guaranteed that is a special array.

#### Output Specification

On one line you are to output the number of special arrays of length that are at least as good as Larry's modulo .

No further constraints.

#### Sample Input

3
1 2 2

#### Sample Output

4