This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D"
#include <bits/stdc++.h>
#include "../../algorithm/longest_increasing_subsequence.hpp"
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = longest_increasing_subsequence(a).size();
cout << ans << '\n';
}
#line 1 "test/aoj/DPL_1_D.test.cpp"
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D"
#include <bits/stdc++.h>
#line 3 "algorithm/longest_increasing_subsequence.hpp"
template <typename T, class Compare>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a,
Compare comp) {
const int n = a.size();
std::vector<T> dp;
std::vector<int> id(n);
for (int i = 0; i < n; i++) {
typename std::vector<T>::iterator it =
std::lower_bound(dp.begin(), dp.end(), a[i], comp);
id[i] = std::distance(dp.begin(), it);
if (it == dp.end()) {
dp.push_back(a[i]);
} else {
*it = a[i];
}
}
std::vector<T> lis(dp.size());
for (int i = n - 1, j = lis.size() - 1; i >= 0; i--) {
if (id[i] == j) {
lis[j--] = i;
}
}
return lis;
}
template <typename T>
std::vector<T> longest_increasing_subsequence(const std::vector<T> &a) {
return longest_increasing_subsequence(a, std::less<T>());
}
#line 6 "test/aoj/DPL_1_D.test.cpp"
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = longest_increasing_subsequence(a).size();
cout << ans << '\n';
}