AsubB
题号：NC303611
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的序列 P，定义 f(A,B)=\begin{cases}1 &若\ A\ 是\ B\ 的子序列\\0& 否则\end{cases} 
求如下式子的值： \sum_{l=2}^{n-1}\sum_{r=l}^{n-1}f(P[l\backsim r],P[1\backsim l-1]+P[r+1\backsim n]) 
\rule{4cm}{0.1pt}
^{\text{∗}} 【子序列】子序列为从原序列中删除任意个（可以为零、可以为全部）元素得到的新序列。
^{\text{∗}} P[l\backsim r] 表示 P 序列中第 l 个元素到第 r 个元素连续一段构成的序列。
^{\text{∗}} + 表示序列拼接，例如 [1,2,4]+[6,7]=[1,2,4,6,7]。

输入描述:

第一行输入一个整数 n(1\leq n \leq 2000)，表示序列长度。

第二行输入 n 个整数 P_i(1\leq P_i\leq 10^9)，表示序列的元素。

输出描述:

输出所求式子的值
示例1

输入

复制 
9
9 9 8 2 4 4 3 5 3

输出

复制 
5

说明

能产生 1 的贡献的 (l,r) 有如下 5 对：
(2, 2)：[9] 是 [9]+[8,2,4,4,3,5,3] 的子序列。
(5, 5)：[4] 是 [9,9,8,2]+[4,3,5,3] 的子序列。
(6, 6)：[4] 是 [9,9,8,2,4]+[3,5,3] 的子序列。
(6, 7)：[4,3] 是 [9,9,8,2,4]+[5,3] 的子序列。
(7, 7)：[3] 是 [9,9,8,2,4,4]+[5,3] 的子序列。