For each input value, maintain tails[length], the smallest possible ending value of an increasing subsequence of that length, and tailIndices[length], the input index that supplies that tail. Binary-search for the first tail greater than or equal to the current value (lower_bound) and replace it. Tails are minimal endpoints, not necessarily a subsequence themselves; their indices let us recover a real subsequence.
Using the first tail >= value makes the subsequence strictly increasing: an equal value replaces the existing tail instead of extending the sequence. Before changing the tails, set the current element’s predecessor to the index stored for the preceding length. This predecessor is earlier in the input and has a smaller value, because that earlier tail was strictly smaller than the current value. When the search reaches position zero, the element starts a subsequence and has no predecessor. Following predecessor links from the index for the final tail reconstructs one longest subsequence in reverse order.
The invariant is that after processing each prefix, tails[k] is the smallest ending value among all increasing subsequences of length k + 1 in that prefix, and tailIndices[k] is an input position having that value. Lower-bound replacement preserves this invariant: a smaller endpoint is at least as extendable, and only a search result at length can increase the best length. The predecessor link captures a valid chain before an endpoint is replaced, so later replacements cannot break reconstruction. Since the input contains at least one value, length is at least one and tailIndices[length - 1] is valid; this also handles N = 1.
Each value uses one binary search and constant-time updates, giving O(N log N) time. The input, tails, tail indices, predecessor indices, and reconstructed answer each use O(N) memory.
import java.io.*;
public class Main {
private static final class FastScanner {
private final InputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int length;
private int position;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) return -1;
}
return buffer[position++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
int[] values = new int[n];
int[] tails = new int[n];
int[] tailIndices = new int[n];
int[] predecessor = new int[n];
for (int i = 0; i < n; i++) {
values[i] = input.nextInt();
predecessor[i] = -1;
}
int length = 0;
for (int i = 0; i < n; i++) {
int value = values[i];
int left = 0;
int right = length;
while (left < right) {
int middle = left + (right - left) / 2;
if (tails[middle] >= value) {
right = middle;
} else {
left = middle + 1;
}
}
int position = left;
if (position > 0) predecessor[i] = tailIndices[position - 1];
tails[position] = value;
tailIndices[position] = i;
if (position == length) length++;
}
int[] answer = new int[length];
int index = tailIndices[length - 1];
for (int i = length - 1; i >= 0; i--) {
answer[i] = values[index];
index = predecessor[index];
}
StringBuilder output = new StringBuilder();
output.append(length).append('\n');
for (int value : answer) output.append(value).append(' ');
System.out.println(output);
}
}