public static int[] lis(int[] array) {
		int[] A = new int[array.length + 1];
		int[] lis = new int[array.length];
		Arrays.fill(A, Integer.MAX_VALUE);
		int longest = 0;
		for (int i = 0; i < array.length; i++) {
			int low = 0;
			int high = array.length - 1;
			while (low < high) {
				int mid = low + (high - low + 1) / 2;
				if (A[mid] >= array[i])
					high = mid - 1;
				else
					low = mid;
			}
			if (A[low + 1] > array[i]) {
				A[low + 1] = array[i];
				longest = (low + 1 > longest) ? low + 1 : longest;
			}
			lis[i] = longest;
		}
		return lis;
	}