const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
for (let i = 0; i < input.length; i += 2) {
let N = input[i]; // 안씀
let array = input[i + 1].trim().split(/\s+/g).map(Number);
let temp = [];
// lower bound. 그러나 이 코드는 모든 값이 중복인 경우 하나씩 확인해야하는 단점이 있다.
// 목표 값이 작은 경우만 고려하고, 크거나 같을 때는 high를 mid로 변경하는 방식이
// 더 효율적이다.
const lower_bound = (target, array) => {
let low = 0;
let high = array.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] === target) {
while (array[mid] === target) mid--;
return mid + 1;
}
if (array[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low;
};
array.forEach((el) => {
if (el > (temp[temp.length - 1] || 0)) {
// 이번 값이 전 값 보다 클때
temp.push(el);
} else {
// temp 값 중에 바꿔줄 수 있는 값 찾기
let location = lower_bound(el, temp);
temp[location] = el;
}
});
console.log(temp.length);
}
