P11771 Attunement is hard

Have you tried to do attunement with the touchpad of a notebook? Aling is playing Tianyi — 's newest X Studio voicebank. Due to the mysterious disappearance of her mouse, it takes an extreme effort for her to adjust every note......

In the note sequence Aling is adjusting is $n$ notes in total. The $i$-th note from the left has a pitch of $s_i$. Aling discovered that three of the notes $s_i,s_j,s_k~(1\le i

N/A

N/A

### Sample Explanation $f(1,2,3)=4$, one of the ideal $(s_i',s_j',s_k')$s is $(2,3,3)$. $f(1,2,4)=13$, one of the ideal $(s_i',s_j',s_k')$s is $(2,2,2)$. $f(1,3,4)=9$, one of the ideal $(s_i',s_j',s_k')$s is $(2,2,2)$. $f(2,3,4)=13$, one of the ideal $(s_i',s_j',s_k')$s is $(3,3,3)$. The sum of the $f(i,j,k)$s is $4+13+9+13=39$. ### Constraints **Subtasks Applied.** You can only gain the score of the subtask if you accepted all the tests in the subtask. | Subtask ID | $n$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $=3$ | No | $5$ | | $2$ | $\le300$ | No | $5$ | | $3$ | $\le900$ | No | $10$ | | $4$ | $\le3\times10^3$ | No | $20$ | | $5$ | $\le5\times10^4$ | No | $20$ | | $6$ | $\le5\times10^5$ | Yes | $20$ | | $7$ | $\le5\times10^5$ | No | $20$ | Special Property: the quantity of different pitches is at most $10$.(i.e. there is at most 10 kinds of pitches.) For all tests, it is guaranteed that $3\le n\le5\times10^5$，$1\le s_i,a,b,c\le 10^9$.