[JSOI2009] 等差数列

题目背景

“一个长度为$l$的数列$a_i$,若相邻两数间的差$a_i - a_{i-1} \ (2 \leq i \leq l)$全部相同,则这个数列为等差数列。”火星特级数学老师jyy,正在给他的火星学生们上数学课。

题目描述

为了检验学生的掌握情况,jyy布置了一道习题:给定一个长度为$N$($1 \leq N \leq 100,000$)的数列,初始时第$i$个数为$v_i$($v_i$是整数,$-100,000 \leq v_i \leq 100,000$),学生们要按照jyy的给出的操作步骤来改变数列中的某些项的值。操作步骤的具体形式为:`A s t a b` ($s, t, a, b$均为整数,$1 \leq s \leq t \leq N$,$-100,000 \leq a, b \leq 100,000$),它表示,在序列的$[s, t]$区间上加上初值为$a$,步长为$b$的等差数列。即$v_i$变为$v_i + a + b \times (i - s)$(对于$s \leq i \leq t$)。 在焦头烂额地计算之余,可怜的火星学生们还得随时回答jyy提出的问题。问题形式为:`B s t`($s, t$均为整数,$1 \leq s \leq t \leq N$),表示jyy询问当前序列的$[s, t]$区间最少能划分成几段,使得每一段都是等差数列。比如说`1 2 3 5 7`最少能划分成$2$段,一段是`1 2 3`,另一段是`5 7`。询问是需要同学们计算出答案后,作为作业交上来的。 虽然操作数加问题数总共只有$Q$($1 \leq Q \leq 100,000$)个,jyy还是觉得这个题很无聊很麻烦。于是他想让你帮他算一份标准答案。

输入输出格式

输入格式


第$1$行:$1$个整数$N$,第$2 \cdots N + 1$行:每行一个整数。第$i + 1$行表示$v_i$。 第$N + 2$行:$1$个整数$Q$,第$N + 3 \cdots N + Q + 2$行:每行描述了一个操作或问题,格式如题中所述,不含引号。

输出格式


若干行,每行一个整数,表示对一个问题的回答。请按照输入中的顺序依次给出回答。

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

**样例说明:** 原数列`1 3 -1 -4 7`。经过操作之后,数列变为`1 2 3 5 7`。如题中所述,最少能划分成$2$段。 **数据规模:** 对$30\%$的数据,$N, Q \leq 5000$。 对$100\%$的数据,$1 \leq N, Q \leq 100,000$。 其他数据范围见题面。