문제 설명

야간 축제의 드론 라이트쇼를 연출합니다. 격납고에 있는 드론들은 각자 정해진 최대 비행 고도를 가지고 있고, 격납고에 놓인 순서대로만 이륙시킬 수 있습니다(중간을 건너뛰는 건 됩니다). 관객이 가장 감탄하는 연출은 "산 모양"입니다. 즉 선택한 드론들의 고도가 한동안 계속 높아지다가, 정점을 찍은 뒤 계속 낮아지는 모양이어야 합니다("바이토닉"). 같은 고도가 연달아 나오면 안 됩니다(엄격히 증가했다가 엄격히 감소). 올라가기만 하거나 내려가기만 해도 산 모양으로 인정합니다. 격납고 순서를 유지하면서 띄울 수 있는 가장 많은 드론의 수를 구하세요.

입력

출력

제약 조건

• •1 ≤ N ≤ 1,000
• •1 ≤ 각 고도 h ≤ 100,000
• •선택한 드론들은 격납고 순서를 유지해야 합니다(연속일 필요는 없음).

예제

6
1 5 2 8 4 3

5

5
3 3 3 3 3

1