F.A.Q
Hand In Hand
Online Acmers
Forum | Discuss
Statistical Charts
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
Virtual Contests
    DIY | Web-DIY beta
Recent Contests
Author ID 
Password 
 Register new ID

Trainsorting

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 629    Accepted Submission(s): 190


Problem Description
Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.

Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.

Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.

Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?
 

Input
The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.
 

Output
Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.
 

Sample Input
3 1 2 3
 

Sample Output
3
 

Source
 

Recommend
chenrui
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2020 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.014000(s) query 2, Server time : 2020-01-25 07:55:08, Gzip enabled