D2: Need help in optimizing a solution

general
,
1

For the lucky draw problem, I have written a java solution with a complexity of O(NlogN) but even this gives a Time limit exceeded error.
How can I further optimize my solution to get it to pass.

import java.io.*;
import java.util.*;

public class D2
{
  public static void main(String [] args)
    throws IOException
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int numTestCases = Integer.parseInt(br.readLine());
    for(int _t=0; _t<numTestCases; ++_t)
    {
      int N = Integer.parseInt(br.readLine());
      StringTokenizer strtok = new StringTokenizer(br.readLine());
      int [] originalArray = new int[N*2];
      for(int i=0; i<N; ++i)
      {
        //this concatenates the array with itself at the time of reading the input itself
        originalArray[i] = originalArray[N+i] = Integer.parseInt(strtok.nextToken());
      }
      //Now we calculate the length of the longest increasing sequence
      int maxWinners = new LongestIncreasingSequence(originalArray).lengthOfLongestIncreasingSequence();
      System.out.println(maxWinners);
    }
  }
}

class LongestIncreasingSequence
{
  int [] array;
  private ArrayList<Integer> longest;
  public LongestIncreasingSequence(int [] A)
  {
    array = A;
    longest = new ArrayList<Integer>();
    longest.add(array[0]);
  }

  public int lengthOfLongestIncreasingSequence()
  {
    for(int i=1; i<array.length; ++i)
    {
      if(array[i] < longest.get(0))
      {
        longest.set(0,array[i]);
      }
      else if(array[i] > longest.get(longest.size()-1))
      {
        longest.add(array[i]);
      }
      else
      {
        //Make the replacement with binary search
        longest.set(getReplacementIndex(array[i]),array[i]);
      }
    }
    return longest.size();
  }

  //Method to find the correct index using binary search
  private int getReplacementIndex(int elem)
  {
    int left, right, mid;
    left = 0; right = longest.size() - 1;
    while(right - left > 1)
    {
      mid = 1 + (right - left) / 2;
      if(array[mid] >= elem)
      {
        if(mid != right) right = mid;
        else --right;
      }
      else
      {
        left = mid;
      }
    }
    return right;
  }
}
2

Hi, this is not an answer in fact, but formatting is not working in comments, so I adding comment as answer…

I tried your LongestIncreasingSequence as

    final int[] a = { 1, 2, 3 };
    final int[] a2 = new int[ 2 * a.length ];
    for ( int i = 0; i < a.length; i++ ) {
        a2[i] = a[i];
        a2[a.length + i] = a[i];
    }
    System.out.println( new LongestIncreasingSequence( a2 ).longest.toString() );

and it prints [1], I think this is not correct. Did I missed something?