int lis(vector<int> array) {
  int size = array.size();
  // initialize
  vector<int> dp(size, 1);

  for (int target = 0; target < size; target++) {
    for (int before = 0; before < target; before++) {
      if (array[before] < array[target]) {
        dp[target] = max(dp[target], dp[before] + 1);
      }
    }
  }

  return dp.back();
}

int lisLength(vector<int>& nums) {
  int size = nums.size();
  vector<int> lis;

  for (int i = 0; i < size; i++) {
    int target = lower_bound(lis.begin(), lis.end(), nums[i]) - lis.begin();

    if (target == lis.size()) {
      lis.push_back(nums[i]);
    } else {
      lis[target] = nums[i];
    }
  }

  // lis 배열에 LIS를 만들기 위해 임시로 사용된 숫자들이 들어있음
  return lis.size();
}

int longestNonDecreasingSubsequence(vector<int> &nums){
  int size = nums.size();
  vector<int> lis;

  for (int i = 0; i < size; i++) {
    int target = upper_bound(lis.begin(), lis.end(), nums[i]) - lis.begin();

    if (target == lis.size()) {
      lis.push_back(nums[i]);
    } else {
      lis[target] = nums[i];
    }
  }

  // lis 배열에 LIS를 구성하는 원소가 들어있음
  return lis.size();
}

struct LIS {
  int index, from;
};

vector<int> longestIncreasingSubsequence(int N, vector<int> array) {
  vector<LIS> lis;
  int lis_cache[MAX] = {
      0,
  };
  int index = 0;

  lis_cache[index] = array[0];
  lis.push_back({0, array[0]});
  for (int i = 1; i < N; i++) {
    if (lis_cache[index] < array[i]) {
      index++;
      lis_cache[index] = array[i];
      lis.push_back({index, array[i]});
    } else {
      int new_index = lower_bound(lis_cache, lis_cache + index, array[i]) - lis_cache;

      lis_cache[new_index] = array[i];
      lis.push_back({new_index, array[i]});
    }
  }

  // index + 1은 LIS 배열의 크기를 의미한다.
  // 역순으로 LIS 배열을 구한다. (index를 이용해 역순으로 구함)
  stack<int> s;
  for (int i = N - 1; i >= 0; i--) {
    if (lis[i].index == index) {
      s.push(lis[i].from);
      index--;
    }
  }

  // stack에 역순으로 저장되어있으므로 뒤집어 LIS 배열을 구함
  vector<int> ret;
  while (!s.empty()) {
    ret.push_back(s.top());
    s.pop();
  }

  return ret;
}