You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

美食遍地，诱惑难抵。

题目描述

李劭鸿来到西伯利亚采购土豆来制作大波浪薯片。为符合大波浪薯片的气质，她每次会让你对战俘营农场进行采购，你要选出一个连续区间，使得这个区间里的土豆数量呈大波浪形状。你需要求出最长的区间长度。

有时候会出现丰收，即给出 $L,R,\Delta$ ，每个区间内的土豆数加上 $\Delta$。

形式化定义：给出每个农场的土豆数 $a_i (i\in[1,n])$，每次询问最长的 $r-l+1([l,r]\subset[1,n])$ 使得满足下列两条之一：

• 要么 $\forall j\in [l,r]$，如果 $j$ 是偶数则 $a_{j-1} < a_j$ 且 $a_j > a_{j+1}$，如果 $j$ 是奇数则 $a_{j-1} > a_j$ 且 $a_j < a_{j+1}$；
• 要么 $\forall j\in [l,r]$，如果 $j$ 是偶数则 $a_{j-1} > a_j$ 且 $a_j < a_{j+1}$，如果 $j$ 是奇数则 $a_{j-1} < a_j$ 且 $a_j > a_{j+1}$。

如果 $j-1$ 或 $j+1$ 在 $[l,r]$ 外则不考虑。

输入格式

整数 $n,m$。

$n$ 个正整数 $a_i$。

$m$ 行描述操作，先给出 $op$。

如果 $op=1$ 则输入 $L,R,\Delta$，描述区间加，否则表示询问。

询问之间相互独立互不影响。

输出格式

对于 $op=2$ 输出答案

2 2
2 2
2
2

1
1

数据范围

对于 $5 \%$ 的数据，$0\leq n,m < 998244353^0$；

对于 $20\%$ 的数据，$0\leq n,m\leq 500$；

对于 $40\%$ 的数据，$0\leq n,m\leq 10^4$；

对于 $70\%$ 的数据，$0\leq n,m\leq 10^5$；

对于 $100\%$ 的数据，$0\leq n,m\leq 10^6$。

输入的其它数保证在 $32$ 位整数内。