Codeforces Round #345 (Div. 1) D. Zip-line

D. Zip-line
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Vasya has decided to build a zip-line on trees of a nearby forest. He wants the line to be as long as possible but he doesn't remember exactly the heights of all trees in the forest. He is sure that he remembers correct heights of all trees except, possibly, one of them.
It is known that the forest consists of n trees staying in a row numbered from left to right with integers from 1 to n. According to Vasya, the height of the i-th tree is equal to hi. The zip-line of length k should hang over k (1 ≤ k ≤ n) trees i1, i2, ..., ik (i1 i2 ik) such that their heights form an increasing sequence, that is hi1 hi2 hik.
Petya had been in this forest together with Vasya, and he now has q assumptions about the mistake in Vasya's sequence h. His i-th assumption consists of two integers ai and bi indicating that, according to Petya, the height of the tree numbered ai is actually equal to bi. Note that Petya's assumptions are independent from each other.
Your task is to find the maximum length of a zip-line that can be built over the trees under each of the q assumptions.
In this problem the length of a zip line is considered equal to the number of trees that form this zip-line.
Input
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 400 000) — the number of the trees in the forest and the number of Petya's assumptions, respectively.
The following line contains n integers hi (1 ≤ hi ≤ 109) — the heights of trees according to Vasya.
Each of the following m lines contains two integers ai and bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ 109).
Output
For each of the Petya's assumptions output one integer, indicating the maximum length of a zip-line that can be built under this assumption.
Examples
input

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

output

4
3
3
4

input

4 2
1 3 2 6
3 5
2 4

output

4
3

Note
Consider the first sample. The first assumption actually coincides with the height remembered by Vasya. In the second assumption the heights of the trees are (4, 2, 3, 4), in the third one they are (1, 2, 3, 3) and in the fourth one they are (1, 2, 3, 5).
최초의 서열을 드리겠습니다. q개의 조작이 있습니다. 모든 조작은 x위치의 수를 y로 바꾸고, 모든 조작 후에 현재의 최장 상승 서열을 출력합니다. (수정은 누적되지 않습니다.)
 
사고방식: 한 위치가 수정된 후에 그는 다음과 같은 세 가지 상황이 나타날 수 있다.
1. 새로운 최장 상승자 서열이 되다
2. 원래 이 위치의 수가 관건적인 위치였다면 이때의 답은 원래의 LIS-1 또는 원래의 LIS일 수 있다
3. 원래의 수가 관건적인 위치가 아니라면 가장 긴 상승자 서열의 길이는 변하지 않는다
 
키 상승 하위 시퀀스 여부를 판단하는 방법:
이 점까지 끝나는 최장 상승 서열 + 이 점부터 시작하는 최장 상승 서열 (이 점 포함하지 않음) 이 최장 상승 서열과 같습니까?
그리고 이 점에서 끝나는 가장 긴 상승자 서열의 길이는 하나밖에 없다.

#include
using namespace std;
const int maxn=400100;
int l[maxn],r[maxn];
int a[maxn],b[maxn],ans[maxn],line[maxn];
struct node{
    int x,y,id;
}Q[maxn];

int DP1(int n,int q){
    int i,len,pos;
    b[1]=a[1];
    l[1]=1,len=1;
    int tot=1;
    while(Q[tot].x==1&&tot<=q){
        ans[Q[tot].id]=1;
        tot++;
    }
    for(int i=2;i<=n;i++){
        while(Q[tot].x==i&&tot<=q){
            pos=lower_bound(b+1,b+len+1,Q[tot].y)-b;
            ans[Q[tot].id]=pos;
            tot++;
        }
        if(a[i]>b[len])
            len=len+1,l[i]=len,b[len]=a[i];
        else{
            pos=lower_bound(b+1,b+len+1,a[i])-b;;
            b[pos]=a[i],l[i]=pos;
        }
    }
    return len;
}

int search(int num,int low,int high){
    while(high-low>=0){
        int mid=(low+high)>>1;
        if(b[mid]<=num)
            high=mid-1;
        else
            low=mid+1;
    }
    return low;
}

void DP2(int n,int q){
    int i,len,pos;
    b[1]=a[n];
    r[n]=0,len=1;
    int tot=q;
    while(Q[tot].x==n&&tot>=1)
        tot--;
    for(int i=n-1;i>=1;i--){
        while(Q[tot].x==i&&tot>=1){
            ans[Q[tot].id]+=search(Q[tot].y,1,len)-1;
            tot--;
        }
        if(a[i]