시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 (추가 시간 없음) 256 MB265897238.710%

문제

수열의 부분수열을 그 수열의 연속한 일부 항을 원래 순서대로 나열해 얻을 수 있는 수열이라고 하자. (원래 부분수열의 정의는 이것이 아니다) 길이 N의 수열 A가 주어지면, 수열 A의 부분수열 중 (부분수열 내 최댓값)-(부분수열 내 최솟값)이 최대가 되는 부분수열 중 가장 짧은 수열의 길이를 구하여라.

입력

첫 줄에 N이 주어진다. (1 ≤ N ≤ 105)

다음 줄에 N개의 수가 공백으로 구분되어 주어지며, i번째 수는 Ai를 뜻한다. (1 ≤ Ai ≤ 105)

출력

문제의 답인 하나의 정수를 출력한다.

예제 입력 1

5
1 1 1 1 1

예제 출력 1

1

예제 입력 2

5
1 1 2 3 3

예제 출력 2

3

출처