substring != subsequence

Why WA????????????????
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;

int a[400000];
int a1[400000],a2[400000];
int s[400000];
int n;

bool cmp(int x,int y)
{
    return a[x]<a[y];
}

int main(void)
{
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    cin >>n;

    if (n<1)return 0;

    for (int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }

    int k1=0,k2=0;

    for (int i=0;i<n-1;i++)
    if (a[n-1]>a[i])
    {
        a1[k1++]=i;
    }
    else
    {
        a2[k2++]=i;
    }

    int t=-1;
    bool f=0;

    if (k2!=0)
    {
        sort(a2,a2+k2,cmp);

        for (int i=k2-2;i>=0;i--)
        {
//        cout << a[a2[i+1]]<< " " << a[a2[i]]<<endl;
            if (a2[i+1]<a2[i])
            {
                if (f)
                {
                    s[++t]=a2[i+1];
                    while (t>=0)cout << a[s[t--]]<< " ";
                }else
                cout << a[a2[i+1]]<< " ";
                f=0;
            }
            else
            {
                s[++t]=a2[i+1];
                f=1;
            }
        }

        s[++t]=a2[0];
        while (t>=0)cout << a[s[t--]]<< " ";
    }
    t=-1;
    f=0;

    if (k1!=0)
    {
        sort(a1,a1+k1,cmp);
        for (int i=k1-2;i>=0;i--)
        {
    //        cout << a[a2[i+1]]<< " " << a[a2[i]]<<endl;
            if (a1[i+1]<a1[i])
            {
                if (f)
                {
                    s[++t]=a1[i+1];
                    while (t>=0)cout << a[s[t--]]<< " ";
                }else
                cout << a[a1[i+1]]<< " ";
                f=0;
            }
            else
            {
                s[++t]=a1[i+1];
                f=1;
            }
        }

        s[++t]=a1[0];
        while (t>=0)cout << a[s[t--]]<< " ";
    }
    cout << a[n-1];


    return 0;
}

Edited by author 27.10.2010 15:51

You shold output results for each number of input meanings, not only for 4. Try using while () { }

Some anti-greedy tests were added. Problem was rejudged (submits from the online contest were not rejudged).
We apologize to all authors who solved this problem using greedy algorithm and got wrong AC verdict because of weak tests.

Why? My program is incorrect. It gives wrong answers on the test above and on many other tests. It's strange that I've got AC.

But test 41 contains something like this:
AGgTta
1
1 6

Right answer is "1".