Background

(From a Phigros illustration, please contact for removal.)

Problem Description

Given a sequence $a$, consider intervals $[l,r]$ such that every number from $a_l$ to $a_r$ appears exactly once within this interval (i.e., all elements in the subarray are pairwise distinct). Suppose there are $t$ intervals that satisfy this requirement, numbered from $[l_1,r_1]$ to $[l_t,r_t]$.

Compute:

Output the answer modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$, the length of the sequence.

The second line contains $n$ non-negative integers, representing the sequence $a$.

Output Format

Output one non-negative integer, the value of the answer modulo $10^9+7$.

6
1 2 3 3 2 1

40

13
1 1 4 5 1 4 1 9 1 9 8 1 0

239

10 
5 4 3 2 5 6 1 3 1 4

315

Hint

Constraints

Special Property A: all $a_i$ are equal.

Special Property B: all $a_i$ are pairwise distinct.

For $100\%$ of the testdata, $1\le n\le2×10^5$ and $0\le a_i\le 10^9$.

Translated by ChatGPT 5