최근 해수면 상승으로 팽수의 고향 남극은 바닷물에 잠겨 소멸될 위기에 놓였다.

팽수는 슬픔에 잠겼지만, 남극의 위기를 제대로 확인하기 위해 해수면 높이에 따른 상태를 알고 싶어졌다.

남극 해안의 높이은 N개의 숫자 h_1,h_2,\cdots,h_N으로 나타낸다. 여기서 i번째 숫자는 i번째 구역의 해안 높이를 의미한다.

팽수는 Q개의 질문이 있다. i번째 질문은 다음과 같다:

만약 해수면이 x_i미터 만큼 상승한다면, l_i지점부터 r_i지점까지 섬이 몇 개가 되는가?

왼쪽 그림은 첫 번째 예제의 첫 번째 질문에 대한 결과이며, 오른쪽 그림은 두 번째 예제의 두 번째 질문에 대한 결과이다. 왼쪽 그림에서 섬은 [2,2], [4,5] 이며, 오른쪽 그림에서 섬은 [1,1], [4,4], [8,8], [10,10] 이다.

섬의 정의는 모든 h_i가 해수면보다 높은 연속된 구역으로 정의되며, 초기 상태는 해수면이 0미터이다.

남극 소멸 timer 2초 memory 512MB

남극 소멸 2초 512MB