cho.sh

Roller Coaster

From a sequence of column heights, delete columns so the survivors strictly decrease then strictly increase (either part may be empty); output the maximum number of survivors.

Medium5Dynamic programmingArrayGreedyTwo pointersInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

The highlight of a roller coaster is the moment the train runs down a slope and climbs back up. Yeongchang designs roller coasters and wants that highlight stretch to be as long as possible.

Building a new coaster costs too much, so Yeongchang bought a used one that is down to its steel columns. The stretch he plans to remodel holds NN columns in a row, and the height of each column is given as a number. Moving a column is expensive, so he only removes columns, and the columns that stay keep their original order.

List the heights of the remaining columns in order. They form a highlight stretch when the heights first keep falling and then keep rising. The slope has to stay smooth, so two neighboring columns cannot have the same height. The rising part may be missing, and the travel direction is decided after the work ends, so a stretch that only falls and a stretch that only rises count the same. When no highlight stretch is possible at all, only the single tallest column stays.

For example, with heights 4 3 5 1 4 2 3, the best choice removes the third column of height 5 and the fifth column of height 4, which leaves 4 3 1 2 3 and keeps 5 columns.

Write a program that computes the largest number of columns that can stay.

Input

The first line has NN, the number of columns in the stretch to remodel. NN is a natural number no greater than 1,000.

The second line has the heights of the NN columns in the order they stand. Each height is a natural number no greater than 10,000.

Output

Print the largest number of columns that can stay.