¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8193
Subtarea

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

Problemas

길이 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의 최댓값을 출력하여라.


Entrada

첫 줄에 수열의 길이 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)


Salida

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


Subtarea

# Puntaje Condición
#115

N\leq 3000, Q\leq 3000

#230

N\leq 40000, Q\leq 40000

#330

N\leq 200000, Q\leq 200000

#425

추가 제한 없음


Ejemplo 

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

Fuente

COCI 2015/2016 Contest #7

Debes iniciar sesión para escribir código.