The treasure expedition has begun, but Captain Smollett doesn’t like anything. Especially the sailors.

There are a total of n sailors on board, each with their own role. The role of the i-th sailor is described by a natural number a_i. The expedition will last for q days, and at the beginning of each day, Captain Smollett plans to change the role of exactly one sailor. After that, by the end of the day, Captain Smollett evaluates his crew and decides which role is the most important, but he does this in a rather unusual way.

Instead of simply choosing the most frequent role, the captain looks for a role x such that the number of subarrays of the roles array a that do not contain role x is as small as possible. Captain Smollett is interested in what the minimum number of subarrays of the roles array a that do not contain role x is. Help the captain calculate this value.

The first line contains two natural numbers n and q — the number of sailors and the number of days of the expedition, respectively (1 ≤ n, q ≤ 10⁵).

The second line contains a sequence of n natural numbers a₁, a₂, …, a_n, where a_i is the role of the i-th sailor (1 ≤ a_i ≤ 10⁹).

The next q lines each contain two numbers s and r — the index of the sailor whose role the captain wants to change, and the new role of this sailor (1 ≤ s ≤ n, 1 ≤ r ≤ 10⁹).

For each of the q days, output one number — the minimum number of subarrays of the roles array a that do not contain a specific role x.

Consider the first example.

1) At the beginning of the first day, the role of the 3rd sailor is changed to 4. The roles array looks like this: [1, 2, 4, 1, 1, 2]. The minimum number of subarrays without role 1 is 4.

2) At the beginning of the second day, the role of the 5th sailor is changed to 4. The roles array looks like this: [1, 2, 4, 1, 4, 2]. The minimum number of subarrays without role 4 is 5. Note that, for example, for the first role, the number of subarrays without it is 6.

3) At the beginning of the third day, the role of the 2nd sailor is changed to 1. The roles array looks like this: [1, 1, 4, 1, 4, 2]. The minimum number of subarrays without role 1 is 4.

4) At the beginning of the fourth day, the role of the 3rd sailor is changed to 1. The roles array looks like this: [1, 1, 1, 1, 4, 2]. The minimum number of subarrays without role 1 is 3.

5) At the beginning of the fifth day, the role of the 6th sailor is changed to 1. The roles array looks like this: [1, 1, 1, 1, 4, 1]. The minimum number of subarrays without role 1 is 1.