#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 
int lengthOfLIS(vector<int>& seq) {
  if (!seq.size()) return 0;
  vector<int> old = seq;
 
  sort(seq.begin(), seq.end());
 
  int longest = 1;
 
  for (int i = 1; i < seq.size(); ++i) {
    if (seq[i] > seq[i-1] && find(old.begin(), old.end(), seq[i]) - old.begin() > find(old.begin(), old.end(), seq[i-1]) - old.begin()) longest++;
  }
  return longest;
}
 
/* Driver program to test above function */
int main() {
	vector<int> v = {1,3,6,7,9,4,10,5,6};
	cout << lengthOfLIS(v) << endl;
	return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgppbnQgbGVuZ3RoT2ZMSVModmVjdG9yPGludD4mIHNlcSkgewogIGlmICghc2VxLnNpemUoKSkgcmV0dXJuIDA7CiAgdmVjdG9yPGludD4gb2xkID0gc2VxOwoKICBzb3J0KHNlcS5iZWdpbigpLCBzZXEuZW5kKCkpOwoKICBpbnQgbG9uZ2VzdCA9IDE7CgogIGZvciAoaW50IGkgPSAxOyBpIDwgc2VxLnNpemUoKTsgKytpKSB7CiAgICBpZiAoc2VxW2ldID4gc2VxW2ktMV0gJiYgZmluZChvbGQuYmVnaW4oKSwgb2xkLmVuZCgpLCBzZXFbaV0pIC0gb2xkLmJlZ2luKCkgPiBmaW5kKG9sZC5iZWdpbigpLCBvbGQuZW5kKCksIHNlcVtpLTFdKSAtIG9sZC5iZWdpbigpKSBsb25nZXN0Kys7CiAgfQogIHJldHVybiBsb25nZXN0Owp9CgovKiBEcml2ZXIgcHJvZ3JhbSB0byB0ZXN0IGFib3ZlIGZ1bmN0aW9uICovCmludCBtYWluKCkgewoJdmVjdG9yPGludD4gdiA9IHsxLDMsNiw3LDksNCwxMCw1LDZ9OwoJY291dCA8PCBsZW5ndGhPZkxJUyh2KSA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0K