Background

2s 512M

Problem Description

Given a positive integer sequence $A_1$, $A_2$, $\cdots$, $A_n$ of length $n$. Define a function $f(l,r)$ as: the number of distinct integers in the subarray whose indices are in the range $[l,r]$. In other words, $f(l,r)$ is the size of the set $\{A_l,A_{l+1},\cdots,A_r\}$. This set is not a multiset, meaning all elements in the set are different.

Now, please compute $\sum_{l=1}^n\sum_{r=l}^n (f(l,r))^2$. Since the answer may be very large, output the result modulo $10^9 +7$.

Input Format

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

The second line contains $n$ positive integers, separated by spaces, representing the sequence $A_1$, $A_2$, $\cdots$, $A_n$.

Output Format

Only one line containing a non-negative integer, representing the answer modulo $10^9+7$.

4
2 1 3 2

43

3
1 1 1

6

Hint

For $10\%$ of the testdata, $1 \leq n \leq 10$.

For $30\%$ of the testdata, $1 \leq n \leq 100$.

For $50\%$ of the testdata, $1 \leq n \leq 10^3$.

For $70\%$ of the testdata, $1 \leq n \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, and each number in the set is in the range $[1,10^9]$.

Translated by ChatGPT 5