夹心饼干

1. 题目描述

给定一个数列$a_1, a_2, \cdots, a_n$，请求出在这个数列中，存在多少个夹心饼干。

所谓夹心饼干，就是从数列中挑出三个数$a_i, a_j, a_k$，满足$i < j < k$且$a_i = a_k$且$a_i \neq a_j$。

2. 输入

2.1 输入格式

• 第一行：单个整数$n$。
• 第二行：$n$个整数表示$a_1, a_2, \cdots, a_n$。

2.2 数据范围

• 30%的数据，$n \leq 100$。
• 60%的数据，$n \leq 20000$。
• 100%的数据，$1 \leq n \leq 300000$，$0 \leq a_i < n$。

2.3 输入样例

5
1 2 1 2 1

3. 输出

3.1 输出格式

单个整数，表示夹心饼干的数量。

3.2 输出样例

5

4.样例说明

对于输入样例 5 1 2 1 2 1，数列$a = [1, 2, 1, 2, 1]$，下面来找出其中的夹心饼干：

• 当$i = 1$，$j = 2$，$k = 3$时，$a_1 = 1$，$a_2 = 2$，$a_3 = 1$，满足$1 < 2 < 3$且$a_1 = a_3$且$a_1 \neq a_2$ ，这是一个夹心饼干。
• 当$i = 1$，$j = 4$，$k = 5$时，$a_1 = 1$，$a_4 = 2$，$a_5 = 1$，满足$1 < 4 < 5$且$a_1 = a_5$且$a_1 \neq a_4$ ，这是一个夹心饼干。
• 当$i = 3$，$j = 4$，$k = 5$时，$a_3 = 1$，$a_4 = 2$，$a_5 = 1$，满足$3 < 4 < 5$且$a_3 = a_5$且$a_3 \neq a_4$ ，这是一个夹心饼干。
• 当$i = 1$，$j = 2$，$k = 5$时，$a_1 = 1$，$a_2 = 2$，$a_5 = 1$，满足$1 < 2 < 5$且$a_1 = a_5$且$a_1 \neq a_2$ ，这是一个夹心饼干。
• 当$i = 2$，$j = 3$，$k = 4$时，$a_2 = 2$，$a_3 = 1$，$a_4 = 2$，满足$2 < 3 < 4$且$a_2 = a_4$且$a_3 \neq a_4$ ，这是一个夹心饼干。

综上，总共能找到$5$个满足条件的夹心饼干组合，所以输出为$5$。