InterviewStreet Triplet optimization I came up with a solution for the InterviewStreet problem "Triplet"

In short, there is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples (d[i] &lt; d[j] &lt; d[k], i &lt; j &lt; k) are present? 

It successfully passes 9 test cases of 15. but my solution exceeds time limit in other test cases.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author Dumindu
 */
public class Triplets {
    public static void main(String args[])
    {
        int[] arr,helper;
        Scanner scn=new Scanner(System.in);
        int x=scn.nextInt();
        arr=new int[x];
        helper=new int[x];
        for(int i=0;i&lt;x;i++)
        {
            arr[i]=scn.nextInt();
        }
        int triplets=0;
        helper[0]=0;
        Map&lt;Integer,Integer&gt; map1=new HashMap&lt;Integer,Integer&gt;();

        for(int i=0;i&lt;x;i++)
        {
            int minVals=0;

            Set&lt;Integer&gt; set=new HashSet&lt;Integer&gt;();
            int tempTrip=0;
            for(int j=i-1;j&gt;=0;j--)
            {   
                if(arr[j]&lt;arr[i] &amp;&amp; !set.contains(arr[j]))
                {
                    minVals++;
                    tempTrip+=helper[j];
                    set.add(arr[j]);
                }
            }
            helper[i]=minVals;
            if(!map1.containsKey(arr[i]))
            {
                triplets+=tempTrip;
                map1.put(arr[i],tempTrip);
            }
            else
            {
                triplets=triplets-map1.get(arr[i])+tempTrip;
            }
        }
        System.out.println(triplets);
    }

}


If there is a way to optimize this solution or approach it differently, please let me know.
The problem looks like it would have a solution of complexity \$O(n log n)\$. Yours has \$O(n^2)\$. google "number of increasing subsequences". 
The site says input size can be \$10^5\$. A \$O(n^2)\$ algorithm with hash look-ups, hash inserts, and virtual function calls in the inner loop will not finish in a few minutes.
By replacing 

int x=scn.nextInt();


with 

int x = 100000;


and

    arr[i]=scn.nextInt();


with

 arr[i] = i + 1;


you can easily test how your program performs with large input.
A quick order of magnitude analysis: An increasing sequence of ~\$10^5\$ elements will have \$~(10^5)^3\$ increasing subsequences of length 3. Since \$10^3 ~= 2^10\$, \$10^15 ~= 2^50\$. \$2^50\$ >> \$2^31\$. So your triplets variable will overflow. It should be an long.