P6477 [NOI Online #2 Senior] Subsequence Problem

2s 512M

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$.

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$.

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

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