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 LIS;
	}