#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
#define MAX_N 1000

#include "LongestIncreasingSubsequence.cpp"

void test1() {
  VI v = {3, 4, 7, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  VI r = lis(v, true);
  for(int i = 0; i < r.size()-1; i++)
	assert(r[i] < r[i+1]);
  assert(r.size() == 10);
}

void test2() {
  VI v = {1, 2, 3, 4, 7, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  VI r = lis(v, false);
  for(int i = 0; i < r.size()-1; i++)
    assert(r[i] <= r[i+1]);
  assert(r.size() == 12);
}

int main() {
  test1();
  test2();
  return 0;
}