역사를 숫자로

알고리즘과 자료구조는 예술, 공예, 과학의 여러 분야에서 쓰인다. 이 문제는 역사 분야의 응용 한 가지를 다룬다.

역사학자들이 어느 도시의 $n$년 동안 도시 발전을 연구하고 있다. 도시 발전은 도시 발전 지수(UDI)라는 종합 지표로 잰다. UDI는 음수를 포함한 정수 값을 가질 수 있다. 각 해 $i$에는 UDI의 초기 추정값 $e_i$가 있다. 새로운 문서와 증거가 발견되면 이 추정값은 수정된다. 역사학자들은 $s_j$년부터 $f_j$년까지(양 끝 포함) 각 해의 UDI 추정값에 $d_j$를 더할 수 있다.

역사학자들은 일정 기간 동안 UDI가 증가해 왔는지 알고 싶어 한다. 표준 정의 대신 다음 절차를 쓴다.

• 연속으로 같은 수가 나오면 하나로 합친다. 예를 들어 1 1 2 2 2 3 3 3은 1 2 3이 된다.
• 변환된 UDI 수열에서 극소점들의 수열이 엄격하게 증가하면, 해 $i$부터 해 $j$까지 UDI가 증가한 것으로 본다. 원소가 양쪽 이웃보다 작으면 극소점이다(첫 원소와 마지막 원소는 이웃이 하나뿐이다).

이 문제에서는 UDI 추정값을 저장하고, 갱신 요청과 확인 요청을 처리하는 시스템을 구현한다.

첫 줄에 기간의 길이를 나타내는 정수 $n$ ($1 \le n \le 3 \cdot 10^5$)이 주어진다.

둘째 줄에 공백으로 구분된 정수 $e_i$ ($-10^8 \le e_i \le 10^8$) $n$개가 주어진다.

셋째 줄에 정수 $m$ ($1 \le m \le 3 \cdot 10^5$)이 주어진다. 이어지는 $m$개의 줄은 다음 요청 중 하나다.

• update에 이어 정수 $s_j$, $f_j$, $d_j$ ($1 \le s_j \le f_j \le n$, $|d_j| \le 10^8$)가 주어진다.
• check에 이어 정수 $s$, $f$ ($1 \le s \le f \le n$)가 주어진다.

check 요청마다 해당 기간에 UDI가 증가했으면 YES, 그렇지 않으면 NO를 출력한다.