CF1209G2 Into Blocks (hard version)

This is a harder version of the problem. In this version $ q \le 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 \le n \le 200\,000 $ , $ 0 \le q \le 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 \le a_i \le 200\,000 $ ), the initial sequence. Each of the following $ q $ lines contains integers $ i_t $ and $ x_t $ ( $ 1 \le i_t \le n $ , $ 1 \le x_t \le 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.