CodeForces - 650D：Zip-line （LIS & DP）

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 h_i. The zip-line of length k should hang over k (1 ≤ k ≤ n) trees i₁, i₂, ..., i_k (i₁ < i₂ < ... < i_k) such that their heights form an increasing sequence, that is h_i₁ < h_i₂ < ... < h_{i_k}.

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 a_i and b_i indicating that, according to Petya, the height of the tree numbered a_i is actually equal to b_i. 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 h_i (1 ≤ h_i ≤ 10⁹) — the heights of trees according to Vasya.

Each of the following m lines contains two integers a_i and b_i (1 ≤ a_i ≤ n, 1 ≤ b_i ≤ 10⁹).

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

Output

Input

Output

4
3

题意：给定一个数组，Q次询问，询问之间彼此独立。每次询问改动一个数，问改动后的LIS。

思路：同今年南京（湘潭）的邀请赛J题，当时思路差不多对了，但是想复杂了，我和陈队花了一个半小时还是写WA了。注意到新LIS和原来的LIS最多相差1。也就是max-1，max，max+1三种情况，那么我们分两步去验证即可：

第一步，考虑没了原来的值：假设原来的LIS一定经过更改点，那么先把ans赋值为max-1；否则赋值ans为max。

第二步，考虑有了新来的值：即用到新的值，那么预处理的时候从前向后后从后向前扫，两遍预处理完，ans=max(ans,f[i]+g[i]-1)。

第二步用线段树或者树状数组即可搞定，常规操作。

第一步，其实也不难想，当时就是这里想复杂了。我们得到LISmax，然后f[i]表示以i为结束的LIS，g[i]表示以i为起点的LIS。如果f[i]+g[i]-1==max，那么种数那么cnt[f[i]]++; 讨论替换i点时，如果cnt[f[i]]==1，则说明原来的LIS必定经过i点。

巴特西

CodeForces - 650D：Zip-line （LIS & DP）

最新文章

热门文章