Happy Birthday

Today it's February 13th. It's a very special day: Miguel's birthday! Like every year, he's organised a big celebration for all his friends. He prepared a succulent dinner at his house. Everyone had a lot of fun
and the celebration was a complete success.

Now it's time for the not-so-funny cleaning up. He wants to start with moving all the dishes from the table to the kitchen. Since he's been going to the gym lately, he feels strong enough to pile and carry at once
as many dishes as he wants. Time doesn't go unnoticed though: he's not as agile as he used to be, so he can only carry the stack of dishes if it's completely stable. A stack of dishes is stable if each dish on the stack is bigger or equal in size than all
the dishes above it. If the stack wasn't stable he would drop the dishes and would have even more things to clean!

At the beginning of the scene, Miguel is empty-handed in one side of the table, walks along the table finding and maybe collecting dishes of different sizes until he reaches the other side, and then brings the collected
dishes to the kitchen. When he finds a dish, he can:

• ignore the dish.
• if he has empty hands, pick up the dish.
• if he has a stack of dishes on his hands, pile the dish on top of the stack.
• if he has a stack of dishes on his hands, put the stack on top of the dish, then pick up the new stack (including the dish).

Miguel is tired, so he wants to clean up the table as soon as possible. He'd like to take as many dishes as he can in each run, but he's exhausted from the party and can't think clearly. He's asked you for help
to find out what the maximum number of dishes he can collect in a single run is.

Input 

Input contains several datasets. Each dataset consists on two lines. The first line of each dataset contains an integer N ( 1N500),
the number of dishes on the table. The second line of each dataset contains N integers, k₁...k_N ( 1k_i1000),
specifying the size of each dish he finds, in the same order he finds them. Input ends with a dataset with N = 0. This case shouldn't be processed.

Output 

For each dataset, print the maximum number of dishes Miguel can collect in a single run.

Sample Input 

6
3 1 5 6 2 4
6
3 4 2 5 2 6
0

Sample Output 

4
6

1 想到求lis和lds不容易，我开始用其他方法写，后来发现行不通，还是只能这个方法。

2 对相同的怎么处理也是一个问题，因为lis和lds中会有重复的，答案偏大。

3 这题写完后又再次明白了自己是有多弱，orz。。。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include <stack>
#include <set>
#include <cstring>
#include <stdlib.h>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 500 + 5;
const int maxk = 1000 + 5;
const int INF = 1000000000;

int k[maxn];
int dplis[maxn], dplds[maxn];

int main(){
    int n;
    while(scanf("%d", &n)){
        if(n == 0) break;
        for(int i = 0;i < n;i++)
            scanf("%d", &k[i]);
        int ans = 0;
        for(int i = n-1;i >= 0;i--){
            int Max = 1;
            for(int j = n-1;j > i;j--){
                if(k[j] >= k[i]){
                    Max = max(Max, dplis[j]+1);
                }
            }
            dplis[i] = Max;

            Max = 1;
            for(int j = n-1;j > i;j--){
                if(k[j] <= k[i]){
                    Max = max(Max, dplds[j]+1);
                }
            }
            dplds[i] = Max;
        }

        for(int i = 0;i < n;i++){
            ans = max(ans, max(dplis[i], dplds[i]));
            for(int j = i+1;j < n;j++){
                if(k[j] > k[i]){
                    ans = max(ans, dplds[i]+dplis[j]);
                }
                if(k[j] < k[i]){
                    ans = max(ans, dplis[i]+dplds[j]);
                }
            }

        }
        printf("%d\n", ans);
    }
    return 0;
}