매일 우유를 만들고자 할 때, 농부 창호의 N(1≤N≤50,000)마리의 소는 항상 같은 순서로 줄을 서고 있다.

편의상 맨 앞에 선 소가 1번, 맨 마지막에 선 소가 N번으로 번호를 매겼다.

어느 날 농부 창호는 몇몇의 소들과 원반던지기 게임을 하고자 한다.

소들을 고르는 방법은 우유를 만들기 위해 줄을 서 있는 소들의 줄에서 임의적으로 한 연속된 구간을 선택해서 게임을 하고자 한다.

게임을 하기 전에 소들의 키가 너무 차이가 날 경우에는 게임이 너무 재미없어지기 때문에 창호는 게임을 하고자 하는 구간을 몇 개 고른 다음에,

해당 구간에 속한 소들의 가장 큰 키와 가장 작은 키의 차이가 얼마나 되는지 알아보고자 한다.

소들의 키가 주어지고, 창호가 알아보고자 하는 Q(1≤Q≤200,000)개의 구간이 주어졌을 때

각 구간에 대한 가장 큰 소와 가장 작은 소의 키 차이를 알아보는 프로그램을 작성하라.

Balanced Lineup timer 1s memory 64MB

Balanced Lineup 1s 64MB