## 2013年8月10日

### 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];
}
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];
}
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;
}
```