MORENA  Morenas Candy Shop ( Easy )
Brunette's Candy Shop ( Easy )
HARDER VERSION: http://www.spoj.com/problems/HILO/
Brunette's is a big candy shop from Little Campina in Paraibas/Brazil. This company is known for making the best candies in the world. Matheus Pheverso is the president of this company and he has a sister called Morena who loves and helps him in running the company. She uses to go the supermarket every day and buy a lot of stuffs to make all the candies. But she's insane and likes to take an alternate path to go to the supermarket.
Given the streets heights, a path is alternate only if the differences between succesive numbers strictly alternate between positive and negative.
Ex:
 Street Heights: {1,3,4,5,2,9,8,10}
 Alternate Paths: {1,3,2,9,8}, {1,4,2,8} {1,5,2,9,8}
Matheus Pheverso is a friendly brother and he would like to know the longest alternate path between the first supermarket and the last supermarket, this means that his sister always starts at the supermarket number 1, and always ends at the last supermarket.
Given the number of supermarkets, and their heights, your task is to print the longest alternate path between the first and the last city.
Input
There is a single positive integer N on the first line of input ( 1 <= N <= 10^6 ) representing the number of supermarkets. In the second line there're N integers Ai representing the heights of each supermarket ( 10^18 <= Ai <= 10^18 ).
Ouput
You have to print the longest alternate path between the first and the last supermarket. The supermarket number 1 is always the first, and the supermarket number N is always the last one.
Example
Input:
5
1 2 3 4 5
Output
2
Input:
8
1 4 2 10 1 9 7 8
Output
8
hide comments
suraj:
20160618 15:33:10
got WA in 9 test case, can someone explain me 1 should be first and n should be last in every test case ya position can be change 

suraj:
20160618 15:25:34
@ryuga you can't change sequence 

ryuga777:
20160611 11:18:19
can anyone explain the sample cases as since the ouptut in second case is 8... so shouldn't the output of the first case will be 3 as  1 3 2 4 5 

rohith:
20141230 17:19:12
@shanmukh yep it is awesome ;P 

:(:
20141230 09:41:57
Awesome problem :)


shantanu:
20140526 19:48:42
Used dp.. WA. submitted like a thousand times. getting all cases right. Last edit: 20140714 20:29:15 

nitish rao:
20131115 14:36:49
Last edit: 20131116 11:22:55 

Ouditchya Sinha:
20130911 06:08:00
Awesome Problem! Finally AC!! :) 

Kevin Sebastian:
20130705 12:05:29
@author I dont understand why I am getting sigsev error submission id 9608166 

SWOOSH!!!:
20130629 09:10:30
@mcd10, I cannot understand how my solution is wrong? I have tested it for larger values as well...Submission id 9572459. Last edit: 20130629 09:30:22 
Added by:  Mateus Dantas [ UFCG ] 
Date:  20120911 
Time limit:  0.181s0.434s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 