32411번 - 계단 수열과 쿼리

임의의 양의 정수 $K$에 대해, 인접한 모든 수 사이의 차이가 $K$인 수열을 $K$-계단 수열이라고 하자. 예를 들어 $[4,5,6,5,6]$은 인접한 모든 수 사이의 차이가 1이므로 $1$-계단 수열이다. 다른 예로 $[17,12,17,22,27]$은 인접한 모든 수 사이의 차이가 5이므로 $5$-계단 수열이다. 길이가 1인 수열은 모든 $K$-계단 수열에 포함된다.

길이가 $N$인 수열 $a_1,a_2,\cdots ,a_N$이 주어질 때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• 1 i j x: 현재 수열의 $i$번째 원소부터 $j$번째 원소까지 각각 $x$를 더한다.
• 2 i j k: $i\le l\le r\le j$이면서, $a_l,a_{l+1},\cdots ,a_r$이 $k$-계단 수열일 때, $r-l+1$의 최댓값을 출력한다.

첫째 줄에 $N$$(1\le N\le 100\, 000)$과 쿼리의 개수 $Q$$(1\le Q\le 100\, 000)$가 공백으로 구분되어 주어진다.

둘째 줄에 정수 $a_1,a_{2},\cdots ,a_N(-10\, 000\le a_i\le 10\, 000)$이 공백으로 구분되어 주어진다.

셋째 줄부터 $Q$개의 줄에 쿼리가 주어진다.

각 쿼리는 네 정수로 이루어져 있으며 $1\ i\ j\ x(1\le i\le j\le N;-1\, 000\le x\le 1\, 000)$ 혹은 $2\ i\ j\ k(1\le i\le j\le N;1\le k\le 10)$이다.

2번 쿼리는 적어도 하나 주어진다.

2번 쿼리가 주어질 때마다 쿼리를 수행한 결과를 한 줄에 하나씩 출력한다.