시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 81 30 24 44.444%

문제

롤러코스터의 하이라이트는 내리막을 쭉 내려와서 다시 올라오는 순간일 것이다. 롤러코스터 설계자인 영창이는 이런 하이라이트 구간을 가장 좋아한다.

영창이는 하이라이트 구간이 길수록 재미있는 롤러코스터이고, 재밌을수록 이용객이 많을 것으로 생각했다.

새로 짓기엔 경제적 부담이 큰 영창이는 철골 기둥만 남은 중고 롤러코스터를 사서 개조하기로 했다.

그런데 이 구간에서 얼마나 긴 하이라이트 구간이 나올지를 모를 지경이던 영창이는 열혈 프로그래머 승균이에게 도움을 청하고자 한다.

우선 영창이는 개조하고자 하는 구간에 있는 각 기둥의 높이를 수치화했다. 이를 통해 하이라이트 구간을 만들려고 한다.

하지만 기둥을 옮기는 비용이 무척 비싸서 세워진 기둥을 최대한으로 남기는 방식으로 공사를 진행하려 한다.

예를 들면, 어떤 구간에 기둥의 높이들이 4 3 5 1 4 2 3 이라면, 높이가 5인 세 번째 기둥과 4인 다섯 번째 기둥을 제거한다면, 4, 3, 1, 2, 3인 기둥만 남아서 가장 긴 하이라이트 구간을 만들 수 있다.

하이라이트 구간으로 만들기 위해 최대한으로 남길 수 있는 기둥의 개수를 구하는 프로그램을 작성하시오.

단, 하이라이트 구간에 다시 올라오는 구간은 없을 수 있다. 그리고 롤러코스터의 진행 방향은 공사가 끝난 후 결정된다.

매끄러운 경사를 위해 연속적으로 높이가 같은 기둥은 없어야 한다.

입력

첫째 줄에 개조하고자 하는 구간의 길이 \(N\)이 주어진다. 구간의 길이는 1,000을 넘지 않는 자연수이다.

둘째 줄에 구간 내에 있는 각 기둥들의 높이가 주어진다. 기둥의 높이는 10,000 이하의 자연수이다.

출력

하이라이트 구간으로 만들기 위해 최대한으로 남길 수 있는 기둥의 개수를 출력한다.

예제 입력

5
5 2 3 2 1

예제 출력

4

힌트