UVa 10534 - Wavio Sequence

#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;
 
struct Num {
  Num() {}
  Num(int value, int index) : value(value), index(index), before(0) {}
  bool operator>(const Num & other) const {
    return value != other.value ? (value > other.value) : (index > other.index);
  }
  bool operator<(const Num & other) const {
    return value < other.value;
  }
  int value, index, before;
};
 
inline void adjust(vector<Num> & v) {
  for (int i = 1; i < v.size(); i++) {
    v[i].before = (v[i].value != v[i - 1].value) + v[i - 1].before;
  }
}
 
int main() {
  int N;
  while (scanf("%d", &N) == 1) {
    Num num[10000];
    for (int i = 0; i < N; i++) {
      int v;
      scanf("%d", &v);
      num[i] = Num(v, i);
    }
    vector<Num> up, down;
    up.PB(num[0]);
    int before[10000] = {}, after[10000] = {};
    for (int i = 1; i < N; i++) {
      if (num[i] > up.back()) {
        up.PB(num[i]);
      } else {
        *lower_bound(up.begin(), up.end(), num[i]) = num[i];
      }
      adjust(up);
      before[up.back().index] = up.back().before;
    }
    down.PB(num[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
      if (num[i] > down.back()) {
        down.PB(num[i]);
      } else {
        *lower_bound(down.begin(), down.end(), num[i]) = num[i];
      }
      adjust(down);
      after[down.back().index] = down.back().before;
    }
    int max = 0;
    for (int i = 0; i < N; i++) {
      int len = (before[i] < after[i] ? before[i] : after[i]) * 2 + 1;
      max = len > max ? len : max;
    }
    printf("%d\n", max);
  }
  return 0;
}