Try On
ПрАнКА 2010
Time Limit: 0.1s, Memory Limit: 64MiB
Ели е експериментатор! Тя пробва какво ли не – от дрехи в мола, до това как ще реагират два опасни химични елемента, смесени в студен чай. Студеният чай принадлежеше на едно момиче, което се беше опитало да сваля Станчо. Миналото време не е случайно.

Освен тези неща, спектърът на нейните експерименти се разпростира дори до точни науки като математиката. Написвайки на един лист последователност от цели числа, тя се пита каква е най-дългата тяхна под-редица, в която разликата между всеки две съседни на всяка стъпка сменя знака си. Такава под-редица тя нарича трионообразна, защото напомня зъбите на трион. Примери за такива редици са (5, -2, 3, -1, 4, -8, -5, -7), (3, 1, 3), (42) и (6, 66). От друга страна (7, 7) и (1, 2, 3) не са.

Нека, например, имаме редицата (13, 5, 3, -2, -2, 3, -1, 4, -8, 42, -5, 16, 19, -7). В нея има много трионообразни под-редици, най-дългите от които са с по десет елемента. Един пример за такава под-редица е (13, -2, 3, -1, 4, -8, 42, 16, 19, -7).

За да не експериментира и върху вас, вие решавате да ѝ помогнете, като напишете програма, която по зададена редица с числа, намира дължината на най-дългата трионообразна под-редица в нея.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – броят числа в редицата. На втория ред следват N на брой цели числа A1, A2, ..., AN – самата редица.
Изход
На стандартния изход изведете едно единствено цяло число - дължината на най-дългата трионообразна под-редица.
Ограничения
  • 1 ≤ N ≤ 1,000
  • -1,000 ≤ Ai ≤ 1,000
Примерен Вход Примерен Изход
4 4 3 1 3 3
3 1 2 3 2
3 6 6 6 1
14 13 5 3 -2 -2 3 -1 4 -8 42 -5 16 19 -7 10
Последният пример е примерът от условието.
Мрън!