Recently, I have been exploring different problems, and I came across an interesting one. Problem Statement

You are given an integer n and an array a of length n. You are also given q queries.

In one operation, you may perform one of the following actions:

Select a strictly increasing subsequence of the array and remove it.

Select a strictly decreasing subsequence of the array and remove it.

Your task is: after each query, determine the minimum number of operations required to remove all elements from the array.

Queries

Each query provides two integers x and val. You must update the array as a[x] = val, then output the answer for the updated array.

Version 1:

1 <= n < 2 * 10^5, q = 0

Version 2:

1 <= n, q <= 2 * 10^5

Note: In this version, operation type 2 (removing a decreasing subsequence) is not allowed.

Version 3:

1 <= n, q <= 2 * 10^5 Both operation types are allowed.