五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式
第一行包含整数$N$，表示景点数量。

第二行包含$N$个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

$2≤N≤1000$

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

二分+单调队列,先求最长上升子序列，再求最长上下降子序列
时间复杂度：$O(nlogn)$：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> f(n + 1, 0), g(n + 1, 0);
    vector<int> d;

    for (int i = 1; i <= n; i++) {
        auto it = lower_bound(d.begin(), d.end(), a[i]);
        if (it == d.end()) d.push_back(a[i]);
        else *it = a[i];
        f[i] = d.size();
    }

    d.clear();

    for (int i = n; i >= 1; i--) {
        auto it = lower_bound(d.begin(), d.end(), a[i]);
        if (it == d.end()) d.push_back(a[i]);
        else *it = a[i];
        g[i] = d.size();
    }

    for (int i = 1; i <= n; i++) ans = max(ans, f[i] + g[i] - 1);

    cout << ans;

    return 0;
}