题目背景

本题和加强版的唯一区别在于数据范围不同

题目描述

现在小A有一个长度为 $n$ 的数列 $a_1,a_2,\cdots,a_n$。
他想要从其中取出一个长度为 $4$ 的子序列 $\{a_{p_1},a_{p_2},a_{p_3},a_{p_4}\}$， 满足 $p_1\lt p_2\lt p_3\lt p_4(1\le p_1\lt p_4\le n)$ 且 $a_{p_1}\lt a_{p_2}=a_{p_3}\lt a_{p_4}$。
问你总共有多少种符合要求的长度为 $4$ 的子序列？

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

10
1 2 3 2 1 3 3 1 2 1

输出 #1

2

说明/提示

样例解释：
取 $p_1=1,p_2=2,p_3=4,p_4=6$，对应子序列为 $\{1,2,2,3\}$。
取 $p_1=1,p_2=2,p_3=4,p_4=7$，对应子序列为 $\{1,2,2,3\}$。
总共 $2$ 种符合要求的长度为 $4$ 的子序列。

对于所有测试点，满足：$1\le n \le 10^5,1\le a_i \le 3$。