#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ull = unsigned long long; using ll = long long; using ld = long double; #define all(v) v.begin(), v.end() #define rep(i, n) for (ll i = 0; i < n; ++i) #define rep2(i, n, m) for (ll i = n; i <= m; ++i) #define rep3(i, n, m) for (ll i = n; i >= m; --i) template using pqg = priority_queue, greater>; template using pq = priority_queue; template inline bool chmax(S &a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(S &a, T b) { if (a > b) { a = b; return true; } return false; } constexpr int INF = 1e9; int n; vector a; int main() { cin >> n; a.resize(n); vector dp(n+1, INF); rep(i, n) { cin >> a[i]; *lower_bound(all(dp), a[i]) = a[i]; } int ans = 0; while (dp[ans] != INF) ++ans; cout << n - ans << endl; return 0; }