Beautiful Sequence

A sequence of integers is called a beautiful sequence if all the integers in it are positive and it is a strictly increasing sequence.
Given a sequence of integers, you have to make it a beautiful sequence. For that you can change any element you want, but you should make as less changes as possible in order to make it a beautiful sequence.
Input
The first line of input is an integer T(T <= 5), the number of test cases. Each test case contains 2 lines.
The first line of the test case contains an integer (0 < N <= 100000), i.e. the number of elements in the original sequence.
The second line contains N positive integers, no larger than 2000000000, which forms the original sequence.
Output
For each test case output the minimal number of elements you must change in the original sequence to make it a beautiful sequence.
Explanation for sample Input/Output
For the 1st test case you needn't to change any elements.
For the 2nd test case you can change 3 into 1 and change 1 into 3.
For the 3rd test case you can change 10 into 1.
For the 4th test case you can change the last three 2s into 3,4 and 5.
UPDATE
Test cases have been made stronger and all previous submissions have been rejudged.

---

Sample Input

4
2
1 2
3
3 2 1
5
10 5 6 7 8
4
2 2 2 2

Sample Output

0
2
1
3

---

Time Limit: 4 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 500 KB 

 

 

Code : 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

class BeautifulNumber {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s;
        int line = 1;
        while ((s = in.readLine()) != null && s.length() != 0) {

            if ( (line != 1) && ((line % 2) == 1) ) {

                String[] p = s.split(" ");
                int[] t = new int[p.length];
                for (int i=0; i<p.length; i++) {
                    t[i] = Integer.valueOf(p[i]);
                }

                int lis = findLIS(t);
                System.out.println((t.length - lis));

            }

            line++;
        }

    }

    public static int search(int[] M, int[] A, int i, int L ) {
        int j = 0;
        int k = L-1;
        while( j <= k ) {
            int m = ( j + k ) / 2;
            if( A[M[m]] <= A[i] ) j = m + 1;
            else k = m - 1;
        }

        return k;
    }

    public static int findLIS(int[] A) {
        int n = A.length;
        int[] M = new int[n];
        int[] P = new int[n];
        M[0] = 0;
        P[0] = -1;
        int L = 1;

        for(int i=1; i<n; ++i) {
            int j = search( M, A, i, L );
            if( j == -1 ) P[i] = -1;
            else P[i] = M[j];

            if( j == L-1 || A[i] < A[M[j+1]] ) {
                M[j+1] = i;
                if( j+2 > L ) L = j+2;
            }
        }

        int[] LIS = new int[L];
        n = L-1;
        int p = M[n];
        while( n >= 0 ) {
            LIS[n] = A[p];
            p = P[p];
            n--;
        }

        return filter(LIS).size();
    }
   
    public static Set<Integer> filter(int[] a) {
       
        Set<Integer> set = new HashSet<Integer>();
        for (Integer i : a)
            set.add(i);
       
        return set;
       
    }
}