ALTSEQ - Alternating Sequences


Given an array a of N integers a1, a2, a3, ... aN you have to find the longest alternating sub-sequence of this array .
An alternating sequence b1, b2 ... bk, k>=1 is a sequence that has the 2 following properties:
1.|b1|<|b2|<|b3|<.....<|bk|
2. The signs alternate between adjacent elements, i.e, if b1 > 0 then b2<0, b3 >0 and so on. Alternatively, if b1<0, then b2>0, b3<0 and so on.
A sub sequence of array a is a sequence obtained by dropping some elements of the array a. Here is the formal definition.
It is guaranteed that the array a contains no element equal to 0.

Constraints

1<=N<=5000 |ai|<=10^9, ai not equal to 0.

Input

The first line contains a single integer N, denoting the size of the array. The next line contains N integers , denoting the array a.

Output

Print a single integer - the length of the longest alternating sub-sequence.

Example

Input:
8
1 2 -2 -3 5 -7 -8 10

Output:
5

Explaination

One of the longest alternating subsequence is 1 -2 5 -7 10


hide comments
kshubham02: 2017-08-30 12:49:41

There is nothing wrong with TC 15, no need of long long int, no problem with max() function, nothing wrong in SPOJ toolkit.

TC 15 is
1
2

output should be 1.

alexandro5432: 2017-08-24 15:20:22

AC in one go...
i have used 32-bit int
no lis only dp with memorisation :)

divush: 2017-08-15 17:13:14

Use long long int if you are stuck on case 15.

deepika10: 2017-07-12 10:19:53

Easy!

ankitshrey112: 2017-06-09 18:04:24

use a little variation in the LIS problem...............AC in 1 go....

Jared León: 2017-04-17 01:40:19

No need for long long in c++. Somehow it gets crazy when the condition ( |ai| > |aj| and (ai > 0 and aj < 0 ) or (ai < 0 and aj>0) ) is used. Instead, the bug free condition (ai > 0 and aj < 0 and ai > -aj) or (ai < 0 and aj > 0 and -ai > aj) is necessary. Most WA in test case 15 are because of bugs and not the algorithm itself.

ahmedcpbl: 2017-04-16 14:54:57

people having WA in test case 15, beware of overflow, (in testing the sign of a number) , cost me 3 WA

vengatesh15: 2017-02-20 12:56:12

silly mistake cost me 1 WA

themast3r: 2017-01-24 18:54:12

Those who are failing the Test Case 15 look at the 1st condition given in problem again.(|b1|<|b2|<|b3|<.....<|bk|)

aimbot: 2017-01-17 19:30:17

@heavenhunter - My tip is to not use spoj toolkit, there are bad test cases there, I modified my code according to that and got a lot of WA (mostly on test 15). And yes, int is enough to hold the array. (I just set the size of dp to 5005 or something a little more than 5000 just in case)

Last edit: 2017-01-17 19:31:35

Added by:Beer hu !!
Date:2016-07-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Hackerrank