int* init_vector(int n, int d) {
  int* a = new int[n];
  for (int i = 0; i < n; i++) a[i] = d;
  return a;
}

void get_path(int* a, int* prev, int max, int* c, int &k) {
  if (prev[max] != max) get_path(a, prev, prev[max], c, k);
  c[k++] = a[max];
}

void lis(int* a, int n, int* c, int &k) {
   int* l = init_vector(n, 0);
   int* prev = init_vector(n, 0);
   l[0] = 1;
   prev[0] = 0;
   for (int i = 1; i < n; i++) {
      int max = i;
      l[max] = 0;
      for (int j  = 0; j < i; j++) {
         if (a[i] > a[j] && l[max] < l[j]) max = j; 
      }
      l[i] = l[max] + 1;
      prev[i] = max;
   }
   int max = 0;
   for (int i = 1; i < n; i++) {
     if (l[max] < l[i]) max = i;
   }
   k = 0;
   get_path(a, prev, max, c, k);
   delete[] l;
   delete[] prev;
}