Train Sorting

Erin is an engineer who also drives trains, and she is responsible for arranging the cars that make up each train. When she orders the cars, she likes to put the heaviest car at the very front of the train and make the weight decrease toward the rear — that is, the weights strictly decrease from front to back.

Inserting a car into the middle of an already-assembled train is impractical, so she never does it. A car may therefore be attached only at the very front or the very back of the train.

The cars arrive at the station in a fixed, predetermined order. As each car arrives, Erin may attach it to the front, attach it to the back, or turn it away without adding it. At every moment, the train must keep its front-to-back decreasing-weight order. Subject to this rule, Erin wants to build a train that is as long as possible (has as many cars as possible).

Given the weights of the cars in the order they arrive at the station, what is the length (number of cars) of the longest train Erin can build?

The first line contains the number of cars $N$ ($0 \le N \le 2000$). Each of the following $N$ lines contains one car's weight, in arrival order; each weight is a non-negative integer. No two cars have the same weight.

Print, on a single line, the length of the longest train Erin can build.