History in Numbers

Algorithms and data structures find their place in various arts, crafts, and sciences. This problem covers one application in history.

Historians study the urban development of a city over a period of $n$ years. Urban development is measured by an aggregate index called the urban development index (UDI), which takes integer values, including negative ones. Each year $i$ starts with an initial estimate $e_i$ of the UDI. As new documents and evidence are found, these estimates are revised. Historians may add $d_j$ to the UDI estimates of every year from $s_j$ to $f_j$ (inclusive).

Historians want to know whether the UDI has been increasing over a period. They use the following procedure instead of the standard definition:

• Collapse every run of consecutive equal numbers into one. For example, 1 1 2 2 2 3 3 3 becomes 1 2 3.
• The UDI is considered increasing from year $i$ to year $j$ if the sequence of local minima in the transformed UDI sequence is strictly increasing. An element is a local minimum if it is less than both of its neighbors (one neighbor for the first or last element).

Implement a system that stores the UDI estimates and processes update and check requests.

The first line contains an integer $n$ ($1 \le n \le 3 \cdot 10^5$), the length of the time period.

The second line contains $n$ space-separated integers $e_i$ ($-10^8 \le e_i \le 10^8$).

The third line contains an integer $m$ ($1 \le m \le 3 \cdot 10^5$). Each of the next $m$ lines is one of the following requests:

• update followed by three integers $s_j$, $f_j$, and $d_j$ ($1 \le s_j \le f_j \le n$, $|d_j| \le 10^8$).
• check followed by two integers $s$ and $f$ ($1 \le s \le f \le n$).

For each check request, print YES if the UDI has been increasing over that period, and NO otherwise.