Zcmu--5083: number pairs of ly (C language)

Description

ly Yes n Number , Now she wants to know this n Take a logarithm out of the number (x,y) Satisfy x%3 <= y%3 What's the number of plans for . among , In this sequence ,x It's better than y front .

Input

Enter two lines , The first line contains a positive integer n , Represents the number of numbers .

The second line contains n A positive integer ,ai Represents the second in the sequence i Number .

Title assurance 1 <= n <= 10^5, 1 <= ai <=10^9

Output

Output one line , It's an integer , For the answer .

Sample Input

4

1  3  4  2

Sample Output

5

analysis ：1. requirement x%3 <= y%3, So we can notice , We can put the whole sequence all %3, Then I found that only 0,1,2 Three situations ！

            2. because x The location should be y front , So the question actually lets us ask each a[ i ] How many of the following sequences are greater than a[ i ] The sum of the number of , So we have to traverse from the back , At the same time, the record is updated 0,1,2 Existing quantity a,b,c. If a[ i]=0, that a[ i ] The contribution to the answer is a+b+c, then a++. If a[i]=1,  Contribution is b+c, then b++,a[i]=2, Contribution is c,c++;

             3. The maximum number of schemes exceeds int 了 , We use long long. 

#include <stdio.h>
int k[100005];
int main()
{
	int n,i,l,a=0,b=0,c=0;	//abc Record the existing 0,1,2 Number  
	long long s=0;	// Record the number of schemes  
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&l),k[i]=l%3;// All modules 3 Deposit in  
	for(i=n-1;i>=0;i--){	// Start from the back  
		if(k[i]==0) s+=a+b+c,a++;
		else if(k[i]==1) s+=b+c,b++;
		else if(k[i]==2) s+=c,c++;
	}
	printf("%lld\n",s);
	return 0;	
}