Pismo
면접 대비시간 제한1초메모리 제한512 MB
정수 배열 A가 주어질 때, L < R인 부분 배열 A[L..R]의 최댓값과 최솟값의 차이를 최소로 만드는 구간의 값을 찾습니다.
문제
Đakovo 근처의 작은 마을에 Kasap이 살고 있다. 농업이 그의 일이자 사랑이자 운명이지만, 여가 시간에는 경쟁 프로그래밍 문제를 풀며 실력이 뛰어나다. 특히 자료 구조를 다루는 문제에 관심이 많다.
어느 맑은 여름날, Kasap의 친구 Mirko가 편지를 보냈고, 그 내용을 그대로 옮긴다.
“친애하는 Kasap,\n> 이 뜨거운 여름날을 잘 견디고 있기를 바라네. 내가 편지를 쓰는 이유는 문제가 하나 있기 때문이야. 며칠 전 한 친구가 어려운 문제를 하나 줬는데 아직 풀지 못했어. 자네가 이런 문제를 좋아한다는 걸 알기에 도움을 청하네. 친구 앞에서 창피당하고 싶지 않거든. 그 문제에는 N개의 정수로 이루어진 배열 A가 있네. 값이 최소인 구간을 찾아야 하네. 구간 [L, R]의 값은 그 구간에 있는 수들의 최댓값과 최솟값의 차이로 정의되네: max(A[L], A[L+1], …, A[R]) - min(A[L], A[L+1], …, A[R]). L이 R보다 엄격히 작은 구간만 본다는 것도 기억해 두게.\n> 고맙네,\n> Mirko”
일주일 동안 문제를 풀었지만 Kasap은 아직 해결하지 못했고, 당신에게 도움을 청한다.
입력
첫째 줄에 양의 정수 N이 주어진다. (2 ≤ N ≤ 100 000)
둘째 줄에 N개의 정수가 주어지며, 각 정수의 절댓값은 10^9보다 작다.
출력
구간의 최솟값을 출력한다.