HILO  High and Low
A student is always bored during his math classes. As the teacher won't let him sleep, he finds something else to do: try to find patterns in the numbers written on the board! Currently, he's spending his time trying to find Hi&Lo subsequences.
Intuitively, a Hi&Lo sequence is any sequence that has consecutive differences with opposite signs, that is, if the first number is greater than the second, then the second is smaller than the third, the third is greater than the fourth, and so on.
Formally, let x[1], x[2], ..., x[n] be the numbers written on the board. A Hi&Lo subsequence of length k that only uses elements from A to B is a sequence of indices a_{1}, a_{2}, ..., a_{k} such that:
 B ≥ a_{k} > ... > a_{2} > a_{1 ≥ }A
 x[a_{i}] x[a_{i1}] != 0, for 1 < i <= k
 ( x[a_{i}]_{ } x[a_{i1}] )( x[a_{i+1}]  x[a_{i}] ) < 0, for 1 < i < k
Note that every sequence with only one element is a Hi&Lo sequence.
However, as the amount of numbers increases, finding a big subsequence is getting harder and harder, so he asked you to create a program to help him and quickly find the largest Hi&Lo subsequence in a given interval.
Input
The input contains several test cases. A test case begins with a line containing integers N (1 ≤ N ≤ 100000) and M (1 ≤ M ≤ 10000), separated by spaces. On the second line there are N positive integers, the initial state of the board. M lines follow, each with an instruction. Instructions can be of two kinds:
1) q A B: Print the length of the longest high & low subsequence only using elements in positions from A to B, inclusive. You may assume that 1 ≤ A ≤ B ≤ N.
2) m A B: Modify the Ath element of the sequence to the positive integer B. You may assume that 1 ≤ A ≤ N.
No number on the board will ever exceed 10^{9}. There is a blank line after each test case. The last test case is followed by a line containing two zeros.
Output
For each instruction of type 1, print a line containing an integer, the answer to the query. After each test, print a blank line.
Example
Input:5 75 7 1 2 3 4 5 q 2 4 m 3 1 q 2 4 m 3 2 q 2 4 m 4 2 q 2 4
0 0
Output: 2 3 2 1
hide comments
Jens Stimpfle:
20140921 21:44:37
1 Fenwick tree (getting the next turnpoint to the left or right in log(n)^2 instead log(n)) seems to be a tiny little faster... 

Jens Stimpfle:
20140921 18:39:12
If you have the stupid idea to solve this with 3 Fenwick trees, be prepared to suffer from 11 assertion failures, 1 wrong answer and 1 TLE during 4 different days while figuring out why your assumptions where wrong :/ 

Singh:
20140121 07:49:00
does the elements of the subsequence should be consecutive? 

Hussain Kara Fallah:
20130910 13:23:54
really hard problem !! 

Alex Abbas:
20130909 18:54:38
Strong, really strong test cases!!! 

Buda IM (retired):
20121223 22:06:01
Yes indeed, cool problem 

:D:
20120929 20:55:21
This one was A LOT of fun. Well done! 

Damian Straszak:
20120923 19:37:03
nice problem 
Added by:  Fernando Fonseca [ITA] 
Date:  20120911 
Time limit:  0.296s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Mateus Dantas 