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
pulkithb: 2020-06-03 19:50:04

easy peasy lemon squeezy ;)

vidhi_5794: 2020-05-11 09:26:53

It is giving me TLE in python

raman_111: 2020-04-26 16:59:37

if you are creating an array and initialising same time without memset that can give you WA on 15 tc

like
arr[n]={0}; -->>this will cause WA on TC 15
use memset
happy coding ;)

mohaimen1: 2020-02-10 14:59:04

I am getting WA in TC 13!...

dhairya_2000: 2019-12-07 19:56:43

AC in 1 GO :)
trivial alteration of LIS problem would result in AC

Last edit: 2019-12-07 19:57:35
sandeepd: 2019-12-06 18:28:03

Input:
5
1 -5 -4 5 -10

Output:
4

tri_cep1: 2019-09-25 21:06:44

behenchodddddd test case 15 kya babasir banai h bc!!!!

shikhar_may7: 2019-08-23 23:35:09

A little variation of LIS, use bottom up dp! (test case 15 won't bother anymore )

shubham97361: 2019-04-28 11:07:16

checking the opposite signs by multiplying elements works fine . Check this test case:
5
-5 -2 4 2 -1

ks1999: 2019-04-11 21:44:50

For everyone who is getting WA, if you are checking if one is negative and other positive with a*b < 0 that is wrong, it is going to overflow, and if says WA at 15th case it doesnt mean that you are wrong at that case, it just means that compiler or what ever reads every test case and after that he evaluate your code.


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