题目描述

给定一个长度为N的数组A=[A$_1$,A$_2$,...A$_N$]，已知其中每个元素A$_i$的值都只可能是1, 2或者3。 请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且A$_i$<A$_j$<A$_k$。

输入格式

第一行包含一个整数N
第二行包含N个整数A$_1$,A$_2$,...A$_N$。(1<=A$_i$<=3)

输出格式

一个整数表示答案

样例

输入

6
1 3 2 1 2 3

输出

3

数据范围与提示

对于30%的数据，1 ≤ N ≤ 100
对于60%的数据，1 ≤ N ≤ 1000 对于100%的数据，1 ≤ N ≤ 100000