Subsequence

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

题目描述

出题人也想写有意思的背景故事。

现有一串长为 $n$ 的序列 $a_1,a_2,...,a_n$ ，求形如 $\begin{matrix}\underbrace{A\cdots A}\\x\end{matrix}\begin{matrix}\underbrace{B\cdots B}\\y\end{matrix}\begin{matrix}\underbrace{A\cdots A}\\x\end{matrix}$ $x,y\ge 0$ 的不同的子序列个数。

$\bullet$ $A,B$ 代表不同的数字，例如 $A=10, B=11$ ；

$\bullet$ 子序列是指满足 $1\le b_1<b_2<...<b_k\le n，0\le k\le n$ 的序列 $a_{b_1},a_{b_2},..,a_{b_k}$ ；

如序列 $[1,2,3,4,5]$ ，可能的子序列有 $[2],[1,3],[2,3,5],[1,2,3,4,5]$ 等，而 $[3,2],[5,4,3,2,1]$ 不是子序列；

$\bullet$ 对于序列 $[1,2,2,1]$ ，满足要求的序列有 $[],[1],[2],[1,1],[2,2],[1,2,1],[1,2,2,1]$ ；

$\bullet$ 相同的序列仅计算一次，例如 $[2],[2]$ 仅计算一次

输入描述:

第一行包含一个整数 ，表示序列  的长度

第二行包含  个数，表示序列 

* 
* 
*

输出描述:

结果占一行，输出答案。

示例1

输入

复制

4
1 2 2 1

输出

复制

示例2

输入

复制

2
1 2

输出

复制

示例3

输入

复制

8
1 1 2 2 3 2 1 1

输出

复制

说明

**样例一说明：