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.

题目描述

牛宝宝喜欢爬坡，但体力不好，他决定用挖掘机把一些山填平，于是牛宝宝将沿途的山路抽象成用单位正方形搭建而成，正方形排成一列搭好，共有n列.牛宝宝决定动用挖掘机了，但是挖掘机只能对正方形进行m次操作

1.U L R yi:将[L,R]列的正方形高度全都改为yi

2.Q L R:查询[L,R]列最长连续上升的列长度

知道[L,R]列最长连续上升的列长度过后，牛宝宝就可以尽情地爬坡了

Ps：连续上升的列长度指对于一段合法区间,都有$x_i<x_{i+1}$。

输入格式

第一行 两个整数n，m；

第二行 n个整数，分别为[1,n]区间每列正方形个数；

接下来m行为m个操作

对于 100%的数据，有1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5 , 1 ≤ xi ≤ 10^8。

输出格式

输出x行，每行为每次操作2的查询结果。

5 4
2 1 2 3 1 
Q 1 4 
Q 2 5 
U 2 4 3 
Q 1 5

3
3
2