题干：

给定一个长度为N的数组A=[A1, A2, ... AN]，已知其中每个元素Ai的值都只可能是1, 2或者3。

请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak。

Input

第一行包含一个整数N  

第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)  

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

对于80%的数据，1 ≤ N ≤ 1000  

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

Output

一个整数表示答案

Sample Input

6
1 3 2 1 2 3

Sample Output

3

解题报告：

     解题的关键在于找到关键元素，“2”，我们每找到一个2，就看看他前面有多少个1，后面有多少个3，乘起来维护一个sum就好了。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll cnt1,cnt3,sum3;
int a[100000 + 5];
int main()
{
	int n;
	ll sum = 0;
	cin>>n;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&a[i]);
		if(a[i] == 3) sum3++;
	}
	for(int i = 1; i<=n; i++) {
		if(a[i] == 1) cnt1++;
		else if(a[i] == 3) cnt3++;
		else {
			sum += cnt1*(sum3-cnt3);
		}
	}
	printf("%lld\n",sum);
	return 0 ;
}

总结：

   注意这题别忘用longlong