Need idea: I thought of finding all possible increasing and decreasing subsequences which is too slow. Can this be done efficiently? Also according to me there can be at max 1 element in common in both the subsequences. I am not getting how to use this information.

If you have time, also tell us why you chose the problems you chose.

Can someone please give me some hints to solve this problem. Thanks in Advance!!

This problem is from ACM Southwestern European Regional Contest, Paris 2003