408058: GYM102968 H KMP

Peter has a sequence $$$S$$$ of numbers of length $$$N$$$ and he wonders how many kompakt subsequences are there in his sequence.

A subsequence of $$$S$$$ is a non-empty sequence $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ with $$$1 \le p_1 < p_2 < \ldots < p_K \le N$$$ for some $$$1 \le K \le N$$$. Two subsequences $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ and $$$S_{q_1}, S_{q_2}, \ldots, S_{q_L}$$$ are different if the sequences $$$p$$$ and $$$q$$$ are different (either $$$K \ne L$$$, of there exists $$$1 \le i \le K$$$ such that $$$p_i \ne q_i$$$).

A sequence is kompakt if it consists only of different values and it contains every integer value between the minimum number in the sequence and the maximum number in the sequence. For example, sequences $$$[1, 2]$$$ and $$$[7, 9, 8]$$$ are kompakt, but sequences $$$[1, 3]$$$ and $$$[7, 9, 6]$$$ are not.

Help Peter count the number of kompakt subsequences in $$$S$$$.

The first line of the input contains $$$1 \le N \le 10^5$$$, the length of the sequence.

The second line of the input contains $$$N$$$ integers, $$$S_1, S_2, \ldots, S_N$$$, representing Peter's sequence.

$$$1 \le S_i \le 10^5$$$ for all $$$1 \le i \le N$$$.

The first line of the input contains $$$1 \le N \le 10^5$$$, the length of the sequence.

The second line of the input contains $$$N$$$ integers, $$$S_1, S_2, \ldots, S_N$$$, representing Peter's sequence.

$$$1 \le S_i \le 10^5$$$ for all $$$1 \le i \le N$$$.

The only line in the output should contain an integer representing the number of kompakt sequences in $$$S$$$. Since the number might be too big, print the answer modulo $$$10^9 + 7$$$.

6
15 16 18 15 8 19

9

8
7 1 9 11 2 10 8 10

26

The kompakt subsequences in the first example are: $$$[15], [16], [18], [15], [8], [19], [15, 16], [16, 15], [18, 19]$$$