Nice SubSegments

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let's call arrays of the form x x+1 ... x+k nice. In other words nice arrays are arrays that form increasing arithmetic progression with the difference of one.
You are given an array of N integers. Let's denote it's numbers by a_{1}, a_{2}, ..., a_{N}. You are also given M change queries. Every change query is a query of the form "X Y" with the meaning that the Xth number in it becomes equal to Y. We perform these queries one after another, strictly in this order. Please, calculate the length of the longest nice subarray of this array, i.e. the length of the longest segment [L; R] that (a_{L}, a_{L+1}, ... a_{R}) is a nice array before all the queries and after every query.
Input
The first line of input consists of two integers N and M, separated by a single space  the length of the array and the number of queries.
The second line of input consists of N integers, the ith equals to a_{i}  namely the ith number in the array.
The following M lines contains the queries in the form "X Y", where X and Y are natural numbers with the meaning that the Xth number becomes equal to Y.
Output
Output the length of the longest nice subarray of the initial array at the first line of output. Then, output M integers at separate lines. The ith such line should contain the length of the longest nice subarray after the ith changing query.
Anytime a_{i} <= 2 * N holds.
Example
Input: 5 5 1 4 3 5 2 2 2 4 4 5 5 3 7 4 8 Output: 1 3 4 5 2 2
Scoring
1 <= N <= 100, 1 <= M <= 1000 : 20 points.
1 <= N, M <= 5000 : 26 points.
1 <= N, M <= 10^{5} : 54 points.
Author:  xcwgf666 
Tester:  
Editorial  http://discuss.codechef.com/problems/SUBSGM 
Tags  easy, greedy, ltime10, segmenttree, xcwgf666 
Date Added:  7032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions