## OCC '19 S4 - Playing with Numbers

View as PDF

Points: 12 (partial)
Time limit: 3.0s
Java 2.75s
Memory limit: 256M

Author:
Problem type

Back when zxyl was young, he enjoyed playing with sequences of numbers but there was always one problem that he could never solve. Now that he's older and has friends like you, he would like you to solve it for him.

Given an array with elements, he would like you to find the length of the longest non-decreasing subarray.

Since zxyl was very smart when he was young, he would like for you to also answer this for queries where in each query he will permanently change an element in the array to become .

#### Input Specification

The first line will contain and .

The second line will contain integers containing the array .

The next lines will contain a query of the form i x, stating that has changed to .

#### Output Specification

Output lines, the length of the longest non-decreasing subarray in for the original array and for each query.

#### Sample Input 1

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

#### Sample Output 1

4
4
3
4

#### Explanation 1

In the original array, the longest non-decreasing subarray is 1 2 3 4.

After the first update, the array is now 2 2 3 4, and the longest non-decreasing subarray is 2 2 3 4.

After the second update, the array is now 2 1 3 4, and the longest non-decreasing subarray is 1 3 4.

After the third update, the array is now 1 1 3 4, and the longest non-decreasing subarray is 1 1 3 4.

#### Sample Input 2

9 3
1 2 3 4 0 1 2 3 4
5 -1
6 5
5 5

#### Sample Output 2

5
5
4
6

#### Explanation 2

In the original array, the longest non-decreasing subarray is 0 1 2 3 4.

After the first update, the array is now 1 2 3 4 -1 1 2 3 4, and the longest non-decreasing subarray is -1 1 2 3 4.

After the second update, the array is now 1 2 3 4 -1 5 2 3 4, and the longest non-decreasing subarray is 1 2 3 4.

After the third update, the array is now 1 2 3 4 5 5 2 3 4, and the longest non-decreasing subarray is 1 2 3 4 5 5.