열차 정렬

에린은 엔지니어이자 기차를 운전하는 기관사입니다. 그녀는 열차를 이루는 차량들을 배열하는 일도 맡고 있습니다. 차량을 정렬할 때, 그녀는 열차의 맨 앞에 가장 무거운 차량을 두고 뒤로 갈수록 무게가 줄어드는 순서, 즉 앞에서 뒤로 무게가 계속 감소하도록 놓는 것을 좋아합니다.

이미 만들어진 열차의 중간에 차량을 끼워 넣는 것은 비현실적이라 하지 않습니다. 따라서 차량은 오직 열차의 맨 앞 또는 맨 뒤에만 붙일 수 있습니다.

차량들은 미리 정해진 순서대로 역에 도착합니다. 각 차량이 도착할 때 에린은 그 차량을 맨 앞에 붙이거나, 맨 뒤에 붙이거나, 받지 않고 보낼 수 있습니다. 단, 어느 시점에서도 열차는 앞에서 뒤로 무게가 감소하는 순서를 유지해야 합니다. 이 조건을 지키면서 에린은 가능한 한 긴(차량 수가 많은) 열차를 만들고 싶어 합니다.

차량들이 역에 도착하는 순서대로 무게가 주어질 때, 에린이 만들 수 있는 가장 긴 열차의 길이(차량 수)를 구하세요.

첫째 줄에 차량의 수 $N$이 주어집니다 ($0 \le N \le 2000$). 이어지는 $N$개의 줄에는 각각 도착 순서대로 차량의 무게가 하나씩 주어지며, 무게는 음이 아닌 정수입니다. 서로 다른 두 차량의 무게가 같은 경우는 없습니다.

에린이 만들 수 있는 가장 긴 열차의 길이를 한 줄에 출력하세요.