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
pratik_gl: 2021-01-13 18:37:54

Initialize all the dp states with 1. Solved the WA in Test Case 15 for me.

distructo: 2020-12-24 08:33:10

just a little variation of LIS, like literally

nfpranta: 2020-12-17 07:19:43

Check for the test case:
7
3 -4 5 -6 7 -1 9
expected output:5
this case helped me overcome error at test case 15
so the approach is for pos number try to find the max of neg increasing subsequence and viceversa

rishav0511: 2020-10-11 20:09:13

what wrong with test case 15 i m getting 2 for i/p-
5
-5 -2 4 2 -1 and
1
2
still showing WA...

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


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