登山 ——最长上升子序列

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

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

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

输入
第一行包含整数 N (2 ≤ N ≤ 1000)，表示景点数量。
第二行包含 N 个整数，表示每个景点的海拔。

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

Input
8
186 186 150 200 160 130 197 220

Output
4

解析：
第一句：所求序列是子序列；
第二句：相邻的两个景点的海拔不能相同，一旦下降，就不能再变大了。
所以行程路线应该是，开始时，严格单调递增，到达顶点后，严格单调递减。
就是求从 1到 i 的最大上升子序列的长度 与 i 到 n 的最大下降子序列的长度之和  的最大值 。

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n;
int a[N],f[N],s[N];
void solve()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        s[i]=1;
        for (int j=1;j<i;j++)
        {
            if (a[j]<a[i]) s[i]=max(s[i],s[j]+1);
        }
    }
    for (int i=n;i>0;i--)
    {
        f[i]=1;
        for (int j=n;j>i;j--)
        {
            if (a[j]<a[i]) f[i]=max(f[i],f[j]+1);
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,s[i]+f[i]-1);
    cout<<ans;
}
signed main()
{
    ios;
    int T=1;
    //cin>>T;
    while (T--) solve(); 
    return 0;
}