思考题 from school

PKU PK P

Given an integer array A of length N.
Define a number is strong if it is not the first or the last number in an array and it is strictly bigger than both the number before and after it.
For example, in the array [2,0,1,7,0,5,1,2] ,the number '7' and '5' are strong numbers.
Define the strong array of an array to be the array deleted the non-strong numbers in the original array.
For example,the strong array of [2,0,1,7,0,5,1,2] is [7,5]
We do the following things: we replace the array with the strong array until the array never changes. Then we call this array the strongest array of the original array.
For example, the strongest array of [1,9,2,6,0,8,1,7,1] is [8]. We find it by: [1,9,2,6,0,8,1,7,1] -> [9,6,8,7] -> [8]
Now given Q queries, each time change exactly one element in A, for each query find out the length of the strongest array of current A.

Example

Input
A=[1,9,2,6,0,8,1,7,1]
Query={
[#9->100],
[#9->2],
[#5->11]
}
Output
3
1
1
Explain
After query 1, A=[1,9,2,6,0,8,1,7,100]->[9,6,8]
After query 2, A=[1,9,2,6,0,8,1,7,2] -> [9,6,8,7] -> [8]
After query 3, A=[1,9,2,6,11,8,1,7,2] -> [9,11,7] -> [11]

Constriants

Subtask1(49%): q=1,n<=1000
Subtask2(1%): q=1,n<=100000
Subtask3(50%):q,n<=100000