시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 (추가 시간 없음) | 256 MB | 265 | 89 | 72 | 38.710% |
수열의 부분수열을 그 수열의 연속한 일부 항을 원래 순서대로 나열해 얻을 수 있는 수열이라고 하자. (원래 부분수열의 정의는 이것이 아니다) 길이 N의 수열 A가 주어지면, 수열 A의 부분수열 중 (부분수열 내 최댓값)-(부분수열 내 최솟값)이 최대가 되는 부분수열 중 가장 짧은 수열의 길이를 구하여라.
첫 줄에 N이 주어진다. (1 ≤ N ≤ 105)
다음 줄에 N개의 수가 공백으로 구분되어 주어지며, i번째 수는 Ai를 뜻한다. (1 ≤ Ai ≤ 105)
문제의 답인 하나의 정수를 출력한다.
5 1 1 1 1 1
1
5 1 1 2 3 3
3