Pismo
레이팅 미적용의견: 0
1 \(s / 64\) \(MB / 70\) points
In a small village besides Đakovo lives Kasap. While agriculture is his branch, love and destiny, in his
free time Kasap solves tasks in competitive programming and is doing very well. Particularly
interesting are the tasks involving data structures.
On a sunny summer day, Kasap's friend Mirko sent him a letter we carry forward entirely:
“My dear Kasap,
I hope you tolerate well these hot summer days. I'm writing this letter because I have a problem.
One friend gave me a hard task the other day that I have not managed to solve yet. Since I know that
you love this sort of tasks, I would ask you for help because I do not want to embarass myself in front
\(of\) \(my\) friend. In the task there is an array A consisting of N integers. You should find an interval of the
minimum value. The value \(of\) the interval [L, R] \(is\) defined \(as\) the difference between the maximum
and minimum value \(of\) the numbers in that interval: max(A[L], A[\(L+1\)], ..., A[R]) - min(A[L], A[\(L+1\)], ...,
A[R]). I will remind you that we observe only the intervals in which L is strictly less than R.
Thank you,
Mirko”
After a week of solving, Kasap has not yet managed to solve the task and asks you to help him.
In the test samples worth 20 points it will hold \(N\) ≤ 100.
In the test samples worth 40 points it will hold \(N\) ≤ 2 000.
In the first line of input there is a positive integer \(N\) (2 ≤ \(N\) ≤ 100 000).
In the second line of input there are \(N\) integers, which absolute value is less than 10 {9}{ }.
Print the minimum value of an interval.
2
1 3
3
1 1 1
5
1 2 1 2 1output
output
2
0
1Explanation of the third test sample:
The maximum at interval [1, 5] is 2, while the minimum on the same interval is 1, so the value of that interval is
2 - 1 = 1, which is also the minimum possible value of an interval.
평가 및 의견
Pismo
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Pismo