#include <bits/stdc++.h>
using namespace std;
vector<int> LIS(const vector<int> &A) {
vector<int> odpoved;
vector<int> konce(1,-(1<<30));
for (int a : A) {
auto kam = lower_bound( konce.begin(), konce.end(), a );
odpoved.push_back( kam - konce.begin() );
if (kam == konce.end()) konce.push_back(a); else *kam = a;
}
return odpoved;
}
 
int main() {
int N;
cin >> N;
vector<int> F(N);
 for (int n=0; n<N; ++n) cin >> F[n];
 vector<int> vysl = LIS(F);
 for (int n=0; n<vysl.size(); ++n) cout << vysl[n] << " ";
 return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvcjxpbnQ+IExJUyhjb25zdCB2ZWN0b3I8aW50PiAmQSkgewp2ZWN0b3I8aW50PiBvZHBvdmVkOwp2ZWN0b3I8aW50PiBrb25jZSgxLC0oMTw8MzApKTsKZm9yIChpbnQgYSA6IEEpIHsKYXV0byBrYW0gPSBsb3dlcl9ib3VuZCgga29uY2UuYmVnaW4oKSwga29uY2UuZW5kKCksIGEgKTsKb2Rwb3ZlZC5wdXNoX2JhY2soIGthbSAtIGtvbmNlLmJlZ2luKCkgKTsKaWYgKGthbSA9PSBrb25jZS5lbmQoKSkga29uY2UucHVzaF9iYWNrKGEpOyBlbHNlICprYW0gPSBhOwp9CnJldHVybiBvZHBvdmVkOwp9CgppbnQgbWFpbigpIHsKaW50IE47CmNpbiA+PiBOOwp2ZWN0b3I8aW50PiBGKE4pOwogZm9yIChpbnQgbj0wOyBuPE47ICsrbikgY2luID4+IEZbbl07CiB2ZWN0b3I8aW50PiB2eXNsID0gTElTKEYpOwogZm9yIChpbnQgbj0wOyBuPHZ5c2wuc2l6ZSgpOyArK24pIGNvdXQgPDwgdnlzbFtuXSA8PCAiICI7CiByZXR1cm4gMDsKfQ==

MwoxIDEgMQo5CjIgNiAzIDQgMSAyIDkgNSA4CjUKNSA0IDMgMiAz

3
1 1 1
9
2 6 3 4 1 2 9 5 8
5
5 4 3 2 3