Problem I
Growing Up is Hard to Do

Apple Bloom, Sweetie Belle and Scootaloo were magically transformed into adults, and while they’re a little concerned, they’re also really excited. They’ll finally be able to do all the fun grown-up things they’ve always wanted to do: stay up late, eat all the snacks they want, travel the world, gamble...

Figure 1: Illustration by Kyle Coate.

Next on their list: the Appleloosa County Fair!

The Appleloosa County Fair spans multiple days. There are $N$ activities at the fair, which are the same for each day; these activities have different opening times (but are also the same for each day), so for simplicity we can order the activities, and assume that if one wants to do two different activities on any given day, say the $i^\text {th}$ and the $j^\text {th}$ activities, then if $i < j$ then the $i^\text {th}$ activity must be done before the $j^\text {th}$ activity and vice-versa.

Each day they visit the fair, they want to choose a subset of the activities to do. Being grown-ups now, of course, they’ve developed a more... nuanced taste for entertainment. In particular, for every day they visit the fair:

1. Apple Bloom wants the activities to be progressively more exciting; they cannot do an activity if its level of excitement is lower than or equal to any activity they have done before on that day.

2. Subject to the above rule, Sweetie Belle wants to do the maximum possible number of activities on each day.

3. Subject to the above two rules, Scootaloo wants to make sure that each visit to the fair is fresh and unique. If today is the $d^\text {th}$ day they visited the fair, and we denote by $s_ i$ the set of the levels of excitement of the activities done on the $i^\text {th}$ day, then $s_ d \neq s_ i$ for all $i < d$.

Figure 2: Illustration of Sample Input 1.

What is the maximum number of days they can visit the fair if they follow the above three requirements?

Input

The first line of input contains a single integer $N$ ($1 \leq N \leq 300\, 000$), the number of activities in the Appleloosa County Fair.

The second line of input contains $N$ integers $A_1, A_2, \dots , A_ N$ ($1 \leq A_ i \leq 10^9$), denoting the levels of excitement of the activities in order.

Output

Output the a single integer on a line by itself, the maximum number of days they can visit the fair if they follow the requirements.

Since this number can be quite large, you should output only the remainder after dividing this number by $10^9+7$.

7
3 2 2 4 5 8 7

4