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

#8536

열대야 주간 2s 1024MB

Problemas

오늘이와 하늘이가 살고 있는 지역은 여름 밤의 최저기온이 M도 이상이면 그날을 '열대야 주간'이라 명명한다.
즉, M = 25 라면 최저기온 표가 [20,43,92,28,29]일 때 2일부터 5일까지가 열대야 주간이다.
이때 최저기온 표에 존재하는 열대야 주간 중 가장 긴 열대야 주간의 길이를 구하고 싶다.

오늘이와 하늘이는 최저기온 표에서 당신에게 두 가지 질문을 할 것이다.

  • 1 L_i\ R_i : 최저기온 표의 L_i 번째 날부터 R_i 번째 날까지 가장 긴 열대야 주간의 길이를 출력한다.

    • 단, 열대야 주간이 존재하지 않는다면 "-1"을 출력한다.

  • 2\ D_i\ T_i : 최저기온 표의 D_i 번째 날의 최저기온을 T_i 로 변경한다.

이때 최저기온 표와 질문이 주어질 때 이를 답변하는 프로그램을 작성하자.


Entrada

첫째 줄에 최저기온 표의 총 날짜 수 N이 주어지며, 다음 N줄에는 그날의 최저기온 T_i가 공백으로 구분되어 주어진다.

그 다음에 질문의 개수 Q와 조건 M이 차례대로 주어진다.

그 바로 아래 줄부터 Q개의 질문 정보가 순서대로 주어진다.

[제약조건]

  • 1 ≤ N, M ≤ 10⁶

  • 1 ≤ Q ≤ 2×10⁵

  • 1 ≤ T_i  ≤ 3×10⁶

  • 1 ≤ D_i , L_i , R_i ≤ N

  • L_i  ≤ R_i


Salida

1번 질문이 주어질 때마다 그에 해당하는 답을 한 줄에 하나씩 출력한다.

  • 1번 질문이 적어도 한 번 주어짐이 보장된다.


Ejemplo 

5
20
43
92
28
29 
4 25
1 1 5
2 3 10
2 1 8
1 1 5
4
2


Fuente

today503213

Debes iniciar sesión para escribir código.