Description

To check how well the students have learned, jyy assigns an exercise: given a sequence of length $N$ ($1 \leq N \leq 100,000$), where initially the $i$-th number is $v_i$ ($v_i$ is an integer, $-100,000 \leq v_i \leq 100,000$), the students must modify some elements according to jyy’s operations. An operation has the form: A s t a b ($s, t, a, b$ are all integers, $1 \leq s \leq t \leq N$, $-100,000 \leq a, b \leq 100,000$). It means: over the interval $[s, t]$, add an arithmetic progression with initial term $a$ and common difference $b$. That is, $v_i$ becomes $v_i + a + b \times (i - s)$ (for $s \leq i \leq t$).

Amid their hectic calculations, the poor Martian students must also answer jyy’s questions at any time. A query has the form: B s t ($s, t$ are integers, $1 \leq s \leq t \leq N$), which asks for the minimum number of segments into which the current interval $[s, t]$ can be partitioned so that each segment is an arithmetic progression. For example, 1 2 3 5 7 can be partitioned into $2$ segments: 1 2 3 and 5 7. The answers to the queries must be computed and handed in as homework.

Although the total number of operations plus queries is only $Q$ ($1 \leq Q \leq 100,000$), jyy still finds this problem boring and troublesome. So he wants you to compute a standard answer for him.

Input Format

Line $1$: one integer $N$. Lines $2 \cdots N + 1$: each line contains one integer. Line $i + 1$ gives $v_i$.

Line $N + 2$: one integer $Q$. Lines $N + 3 \cdots N + Q + 2$: each line describes an operation or a query, in the format described above, without quotes.

Output Format

Several lines, each containing one integer, representing the answer to a query. Output the answers in the same order as the queries appear in the input.

5
1
3
-1
-4
7
2
A 2 4 -1 5
B 1 5

2

Hint

Sample explanation:

The original sequence is 1 3 -1 -4 7. After the operation, the sequence becomes 1 2 3 5 7. As described above, the minimum number of segments is $2$.

Constraints:

• For $30\%$ of the testdata, $N, Q \leq 5000$.
• For $100\%$ of the testdata, $1 \leq N, Q \leq 100,000$.

Translated by ChatGPT 5