長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。次のクエリを処理するプログラムを作成せよ。

• $1$ $i$ $j$ $x$ $y$ : $A_i, A_{i+1}, \ldots, A_j$ に初項 $x$, 公差 $y$ の等差数列を加える。($1 \le i \le j \le N$, $-100{,}000 \le x, y \le 100{,}000$)
• $2$ $i$ $j$ : $i \le l < r \le j$ かつ $A_l, A_{l+1}, \ldots, A_r$ が等差数列となる最長の連続部分列の長さを出力する。($1 \le i < j \le N$)

入力

1行目に数列の長さ $N$ ($2 \le N \le 100{,}000$) が与えられる。

2行目に $A_1, A_2, \ldots, A_N$ が与えられる。($-100{,}000 \le A_i \le 100{,}000$)

3行目にクエリの個数 $M$ ($1 \le M \le 100{,}000$) が与えられる。

4行目以降の $M$ 行にクエリが与えられる。

すべての入力は整数である。

出力

2番目のクエリごとに答えを1行ずつ出力する。

入出力例

入力例 1

5
1 2 3 4 5
4
2 1 5
1 3 4 1 1
2 1 5
2 3 5

出力例 1

5
3
2