提示: 欢迎访问OurACM平台。
Problem 2059 MM

Accept: 124    Submit: 524
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There is a array contain N(1<N<=100000) numbers. Now give you M(1<M<10000) query.

Every query will be:

1 x : ask longest substring which every number no less than x

2 y x : change the A[y] to x. there are at most change 10 times.

For each ask can you tell me the length of longest substring.

Input

There are multiple tests.

each test first line contain two integer numbers N M,second line contain N integer numbers.

Next M lines each line will be:

1 x : ask longest substring which every number no less than x

2 y x : change the A[y] to x. there are at most change 10 times.

0 < N <= 100000, 0 < M <= 10000, -1000000000 <= A[i] <= 1000000000

Output

Each ask output the length of longest substring .

Sample Input

5 5 1 2 3 2 1 1 2 1 3 2 3 1 1 2 1 3

Sample Output

3 1 1 0

Source

FOJ有奖月赛-2011年11月

Submit  Back  Status  Discuss