LCS.java

importjava.io.*;
importjava.util.*;
importjava.text.*;
importjava.math.*;
importjava.util.regex.*;

classA {

staticintCeilIndex(intA[], intl, intr, intkey) 
 {
intm;

while( r - l > 1 ) {
m = l + (r - l)/2;
if(A[m] <= key ) 
r = m;
else
l = m;
 }

returnr;
}

staticintLongestIncreasingSubsequenceLength(intA[], intsize) {

int[] tailTable = newint[size];
intlen;

for(inti=0;i<size;++i)
tailTable[i] = 0;

tailTable[0] = A[0];
len = 1;
for( inti = 1; i < size; i++ ) {
if( A[i] > tailTable[0] )
tailTable[0] = A[i];
elseif( A[i] < tailTable[len-1] )

tailTable[len++] = A[i];
else
tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];
 }

returnlen;
}

publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);
intN = sc.nextInt();
int[] arr = newint[N];

for(inti=0;i<N;++i)
arr[i] = sc.nextInt();
longn = LongestIncreasingSubsequenceLength(arr, N);
n= n*(n-1)*(n-2);
n/=6;
System.out.println(n);

}
}