MORENA - Morenas Candy Shop ( Easy )

HARDER VERSION: 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 successive numbers strictly alternate between positive and negative.

Example:

- 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).

Output

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

Added by:Mateus Dantas [ UFCG ]
Date:2012-09-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-05-26 19:48:42 shantanu
Used dp.. WA. submitted like a thousand times. getting all cases right.

Last edit: 2014-07-14 20:29:15
2013-09-11 06:08:00 Ouditchya Sinha
Awesome Problem! Finally AC!! :)
2013-07-05 12:05:29 Kevin Sebastian
@author I dont understand why I am getting sigsev error submission id 9608166
2013-06-29 09:10:30 SWOOSH!!!
@mcd10, I cannot understand how my solution is wrong? I have tested it for larger values as well...Submission id 9572459.

Last edit: 2013-06-29 09:30:22
2013-06-18 20:13:30 Aditya Bahuguna
Whoa!//scanf VS cin ..>1 sec time diff
2012-10-16 10:28:02 Nitin Khanna
Can Ai be Negative? If yes what will be output for
3
1 -1 1
3
-1 1 -1
?
2012-09-30 02:30:28 Mateus Dantas [ UFCG ]
Yes, the test case:
5
4 1 1 1 1

gives the answer 2.
The longest path refer to the maximum lenght that you can get by any alternate subsequence.
2012-09-29 21:43:01 :D
The definition of the alternating path is the same as for HILO problem. In fact you can convert the data here to:
N 1
a1 a2 ... aN
q 1 N

pass it to HILO, and you should get the same result. David Moran, sorry, but you "clarification" is all wrong.

As for the case where all elements are the same, my program would give 1. I think MateusDantas was thinking about: "5\n 4 1 1 1 1\n" and not "4\n 1 1 1 1\n".
2012-09-20 23:00:03 le derp!!
longest path refer to length here?
2012-09-15 11:16:20 ♘Prabhat
can anyone explain why ans of 4 1 1 1 1 is 2

Last edit: 2012-09-16 00:27:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.