페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8193
서브태스크

수열과 신나는 쿼리 4s 1024MB

문제

길이 N의 수열 A_1, A_2, A_3, ..., A_N이 주어진다.

다음과 같은 쿼리를 Q개 처리하여, 답을 순서대로 한 줄에 하나씩 출력하여라.

  • 각 쿼리는 l r 의 형태로 주어진다.

  • l\leq s\leq e\leq r이면서, 모든 s\leq i\leq e인 A_i에 대해 min(A_s, A_e)\leq A_i\leq max(A_s, A_e)를 만족하는 (s, e) 쌍 중, e-s+1의 최댓값을 출력하여라.


입력

첫 줄에 수열의 길이 N이 주어진다. (1\leq N\leq 500000)

다음 줄에 수열 A_1, ..., A_N이 차례로 주어진다. (1\leq A_i\leq 10^9)

다음 줄에 쿼리의 개수 Q가 주어진다. (1\leq Q\leq 500000)

다음 Q개의 줄에 걸쳐 쿼리가 l r꼴로 공백으로 구분되어 주어진다. (1\leq l\leq r\leq N)


출력

각 쿼리에 대한 답을 한줄에 하나씩 순서대로 출력하여라.


부분문제

번호 점수 조건
#115점

N\leq 3000, Q\leq 3000

#230점

N\leq 40000, Q\leq 40000

#330점

N\leq 200000, Q\leq 200000

#425점

추가 제한 없음


예제 

6
6 6 5 1 6 2
4
4 5
4 6
1 4
2 3
2
2
4
2

출처

COCI 2015/2016 Contest #7
로그인해야 코드를 작성할 수 있어요.