题目描述

小敏种了一排N（1<=N<=100000）个相邻（连续）的树苗，每个树苗i的初始高度为ai(ai是整数，1<=ai<=100000)。小敏有时候给\([\)l,r\(]\)区间的树苗浇水，这个区间的所有树苗就会长高h。但小敏有强迫症，她看不惯树木参差不齐，于是她想去掉一些树苗，使剩下相邻的树苗都一样高。小敏望向窗户发呆的时候，总是想着在\([\)l,r\(]\)区间内，如何去掉最少的树苗，使剩下相邻的树苗都一样高。她请你来解决这个问题。

输入数据

第一行，一个整数N。
第二行，有N个整数ai。
第三行，一个整数Q，代表小敏浇水次数和询问你次数的总和
下面Q行， 每一行形式如 1 s t h的，代表小敏在\([\)s,t\(]\)区间浇水，区间内树苗长高了h；
形式如2 s t的，代表小敏询问你在\([\)s,t\(]\)区间内，如何去掉最少的树苗，使剩下相邻的树苗都一样高。(只是无聊的问，并没有真的去掉)。

输出数据

若干行，每行一个整数代表你对小敏一个询问的回答（即最少去掉几棵树）。

输入

5
1 3 4 6 8
2
1 3 4 2
2 1 5

输出

2

样例解释：初始高度为1 3 4 6 8，将\([\)3，4\(]\)区间的树浇水后变为1 3 6 8 8，去掉第2和第3棵树，使剩下相邻的树苗{1}{8 8}每组都一样高。

说明/提示

数据规模与约定
对于 30% 的数据：N，Q<=5000。
对于 100% 的数据：N，Q<=100000。
对于所有数据 1<=s<=t<=N；1<=h<=100000，都为整数；