B'This is a harder version of the problem. In this version q <= 200 ,000 . A sequence of integers is called nice if its elements are arranged in blocks like in [3, 3, 3, 4, 1, 1] . Formally, if two elements are equal, everything in between must also be equal. Let 's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value x to value y , you must also change all other elements of value x into y as well. For example, for [3, 3, 1, 3, 2, 1, 2] it isn 't allowed to change first 1 to 3 and second 1 to 2 . You need to leave 1 's untouched or change them to the same value. You are given a sequence of integers a_1, a_2, ldots, a_n and q updates. Each update is of form " i x " -- change a_i to x . Updates are not independent (the change stays for the future). Print the difficulty of the initial sequence and of the sequence after every update. The first line contains integers n and q ( 1 <= n <= 200 ,000 , 0 <= q <= 200 ,000 ), the length of the sequence and the number of the updates. The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= 200 ,000 ), the initial sequence. Each of the following q lines contains integers i_t and x_t ( 1 <= i_t <= n , 1 <= x_t <= 200 ,000 ), the position and the new value for this position. Print q+1 integers, the answer for the initial sequence and the answer after every update. '...