2013
11-12

# Crazy Thairs

These days, Sempr is crazed on one problem named Crazy Thair. Given N (1 ≤ N ≤ 50000) numbers, which  are no more than 109, Crazy Thair is a group of 5 numbers {i, j, k, l, m} satisfying:

1. 1 ≤ i < j < k < l < m N
2. Ai < Aj < Ak < Al < Am

For example, in the sequence {2, 1, 3, 4, 5, 7, 6},there are four Crazy Thair groups: {1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 3, 4, 5, 7} and {2, 3, 4, 5, 7}.

Could you help Sempr to count how many Crazy Thairs in the sequence?

Input contains several test cases. Each test case begins with a line containing a number N, followed by a line containing N numbers.

Output the amount of Crazy Thairs in each sequence.

5
1 2 3 4 5
7
2 1 3 4 5 7 6
7
1 2 3 4 5 6 7

1
4
21

//* @author: ccQ.SuperSupper
import java.util.*;
import java.math.*;

class Binary
{
int n,i;
long ret;
long a[],c[];
void init(int x)
{
n = x;
a = new long [x+10];
c = new long [x+10];
for(i=0;i< x+10;++i)
{
a[i]=c[i]=0;
}
}
void update(int x,long v)
{
a[x]+=v;
for(i=x;i<=n;i+=lowbit(i)) c[i]+=v;
}
int lowbit(int x)
{
return (x)&(-x);
}
long query(int x)
{
for(ret=0,i=x;i>0;i^=lowbit(i)) ret+=c[i];
return ret;
}
}
public class Main {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int n,i,j;
int way[] = new int[50010];
int num[] = new int[50010];
int mapping[]= new int[50010];

BigInteger ans,temp;

Binary array[] = new Binary[5];

Scanner cin = new Scanner(System.in);
while(cin.hasNext())
{
n = cin.nextInt();
for(i=0;i< n;++i)
{
way[i]=cin.nextInt();
num[i]=way[i];
}
Arrays.sort(num,0,n);
mapping[0]=2;
for(i=1;i< n;++i)
{
if(num[i]==num[i-1]) mapping[i]=mapping[i-1];
else mapping[i]=mapping[i-1]+1;
}

for(i=0;i< n;++i)
{
way[i]=mapping[binary_search(0,n-1,way[i],num)];
}
for(i=0;i< 5;++i)
{
array[i]=new Binary();
array[i].init(50010);
}

ans = new BigInteger("0");
for(i=0;i< n;++i)
{
for(j=4;j>0;--j)
{
array[j].update(way[i], array[j-1].query(way[i]-1));
}
array[1].update(way[i], 1);

temp = BigInteger.valueOf(array[4].query(way[i]-1));
}

System.out.println(ans);

}
}
public static int binary_search(int left,int right,int value,int num[])
{
int mid;
while(left+1< right)
{
mid=(left+right)/2;
if(num[mid]>value) right = mid;
else left = mid;
}
if(num[left]==value) return left;
return right;
}

}