123

题目描述

给你一个只含 $1,2,3$ 的数组，计算有多少个子序列为 $\{1,2,3\}$。

*子序列：从一个序列中删除若干（也可以不删除）元素后，剩下的元素按原来的顺序排列形成的新序列。

输入格式

第一行一个整数 $n$（$1 \le n \le 10^5$），表示数组长度。 第二行 $n$ 个整数，表示数组内容。

输出格式

一个整数，表示子序列 "123" 的个数。

样例 1

6
1 1 2 3 1 2

2

提示

样例中有两个子序列 "123"，分别是下标$(1,3,4)$和$(2,3,4)$。