Try the test
8
1 7 4 6 3 5 2 8
and
8
8 2 5 3 6 4 7 1
.
Both tests have solutions.

I spent a lot of time on this problem.
For those who want to fit the time limit I recommend reading A. Brandstƒadt, D. Kratsch "On partitions of permutations into increasing and decreasing subsequences".
Also M.D. Atkinson "Permutations which are the union of an increasing and a decreasing subsequence" is very interesting to read but not so helpful for this particular problem.

5
1 2 3 4 5
shold be
4 1
1 2 3 4
5
(or others)
but can't be
5 0
1 2 3 4 5

its a greedy+dp according to me

you should analyze the four scenario like

1. two increasing sequence :

     take two array . two array initially have only one value zero. then iterate over 2nd to nth element.

     if element > 1st and 2nd arrays last element
             then, 1st sequence last element > 2nd arrays last element then: (add element
                                                                  to the 1st array)
             otherwise (add element to the 1st array)
     otherwise   add it to the array whose last element < element

     (this is optimal ).

2. two decreasing sequence: approach greedily like 1st one

3. one increasing and one decreasing(1st element included in the increasing array):(try yourself)

4. one increasing and one decreasing(1st element included in the decreasing array):(try yourself)

for 3rd and 4th criteria , think greedily also.

New tests have been added. 13 authors have lost AC after rejudge.

Edited by author 05.08.2013 10:00