testgen

#include <iostream>
#include <string>
#include <sstream>
#include <vector>


using std::vector;
using std::stringstream;

const int INF = 2e9;

stringstream solve1(std::istream &cin) {
  stringstream cout;
  int n, k = 0; cin >> n;
  vector<int> v(n);
  for (int &el : v) cin >> el;
  vector<int> dp(n, INF);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (dp[j] >= v[i]) {
        dp[j] = v[i];
        break;
      }
    }
  }
  for (int &el : dp) {
    if (el != INF) k++;
    else break;
  }
  cout << k;
  return cout;
}

stringstream solve2(std::istream &cin) {
  stringstream cout;
  int n, k = 0; cin >> n;
  vector<int> v(n);
  for (int &el : v) cin >> el;
  vector<int> dp(n, INF);
  for (int i = 0; i < n; ++i) {
    int l = 0, r = n - 1, m;
    while (r - l > 1) {
      m = (l + r) / 2;
      if (dp[m] <= v[i]) l = m;
      else r = m;
    }
    if (dp[l] > v[i])
      dp[l] = v[i];
    else if (dp[r] > v[i])
      dp[r] = v[i];
  }
  for (int &el : dp) {
    if (el != INF) k++;
    else break;
  }
  cout << k;
  return cout;
}

int randint(int from, int to) {
  return from + (rand()%(to - from));
}

#include "func.h"

int main() {
  int n; std::cin >> n;
  srand(n);
  stringstream test1 = testgen(n), test2;
  test2 = stringstream(test1.str());
  stringstream ans1 = solve1(test1), ans2 = solve2(test2);
  std::cout << (ans1.str() == ans2.str());
}