思考题 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