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

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;

int BIT3[1024], BIT4[1024];
void modify(int idx, int val, int b[]) {
    while(idx <= 1005) {
        b[idx] = max(b[idx], val);
        idx += idx&(-idx);
    }
}
int query(int idx, int b[]) {
    int ret = 0;
    while(idx) {
        ret = max(ret, b[idx]);
        idx -= idx&(-idx);
    }
    return ret;
}
int main() {
    //freopen("in.txt","r+t",stdin);
    //freopen("out2.txt","w+t",stdout);
    int n, A[505];
    int i, j, k;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            scanf("%d", &A[i]), A[i]++;
        memset(BIT3, 0, sizeof(BIT3));
        memset(BIT4, 0, sizeof(BIT4));
        int LIS2[505], LDS2[505]; // <=, >=
        int ret = 0;
        for(i = n-1; i >= 0; i--) {
            LIS2[i] = query(1005 - (A[i]), BIT3) + 1;
            LDS2[i] = query(A[i], BIT4) + 1;
            ret = max(ret, query(1005 - (A[i]+1), BIT3)+1+LDS2[i]-1);
            ret = max(ret, LIS2[i]+query(A[i]-1, BIT4)+1-1);
            modify(1005 - A[i], LIS2[i], BIT3);
            modify(A[i], LDS2[i], BIT4);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
6
3 1 5 6 2 4
6
3 4 2 5 2 6
6
3 3 4 3 2 1
10
3 4 3 6 8 8 10 5 10 1
10
8 7 6 5 10 5 8 9 5 4
*/