Unique Array
Contest: Educational Codeforces Round 165 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, divide and conquer, dp, greedy

You are given an integer array $$$a$$$ of length $$$n$$$. A subarray of $$$a$$$ is one of its contiguous subsequences (i. e. an array $$$[a_l, a_{l+1}, \dots, a_r]$$$ for some integers $$$l$$$ and $$$r$$$ such that $$$1 \le l < r \le n$$$). Let's call a subarray unique if there is an integer that occurs exactly once in the subarray.

You can perform the following operation any number of times (possibly zero): choose an element of the array and replace it with any integer.

Your task is to calculate the minimum number of aforementioned operation in order for all the subarrays of the array $$$a$$$ to be unique.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the minimum number of aforementioned operation in order for all the subarrays of the array $$$a$$$ to be unique.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the second test case, you can replace the $$$1$$$-st and the $$$3$$$-rd element, for example, like this: $$$[3, 4, 1, 4]$$$.

In the third test case, you can replace the $$$4$$$-th element, for example, like this: $$$[3, 1, 2, 3, 2]$$$.

Example input:
4
3
2 1 2
4
4 4 4 4
5
3 1 2 1 2
5
1 3 2 1 2

Example output:
0
2
1
0

Editorial:
When we replace an element, we can always choose an integer that is not present in the array. So, if we replace the $$$i$$$-th element, every subarray containing it becomes unique; and the problem can be reformulated as follows: consider all non-unique subarrays of the array, and calculate the minimum number of elements you have to choose so that, for every non-unique subarray, at least one of its elements is chosen.
We can use the following greedy strategy to do it: go through the array from left to right, maintaining the index $$$s$$$ of the last element we replaced. When we consider the $$$i$$$-th element of the array, if there is a non-unique subarray $$$[l, r]$$$ with $$$l > s$$$, we replace the $$$i$$$-th element, otherwise we don't replace anything.
Why is it optimal? Essentially, this greedy approach always finds a non-unique subarray $$$[l, r]$$$ with the lowest value of $$$r$$$, and replaces the $$$r$$$-th element. We obviously have to replace at least one element from the subarray $$$[l, r]$$$; but replacing the $$$r$$$-th element is optimal since we picked the lowest value of $$$r$$$, so every non-unique subarray which contains any element from $$$[l, r]$$$ also contains the $$$r$$$-th element.
Okay, but we need to make this greedy solution work fast. When we consider the $$$i$$$-th element, how do we check that there's a non-unique subarray starting after the element $$$s$$$ and ending at the $$$i$$$-th element? Suppose we go from the $$$i$$$-th element to the left and maintain a counter; when we meet an element for the first time, we increase this counter; when we meet an element for the second time, we decrease this counter. If this counter is equal to $$$0$$$, then the current subarray is non-unique: every element appears at least twice. Otherwise, at least one element has exactly one occurrence.
Suppose we maintain an array $$$t$$$ where for each integer present in the original array, we put $$$1$$$ in the last position we've seen this element, and $$$-1$$$ in the second-to-last position we've seen this element (i. e. for every element, we consider its two last occurrences among the first $$$i$$$ positions in the array, put $$$1$$$ in the last of them, and $$$-1$$$ in the second-to-last of them). Then, if we go from $$$i$$$ to $$$l$$$ and maintain the counter in the same way as we described in the previous paragraph, the value of this counter will be equal to the sum of the corresponding segment in this array $$$t$$$.
So, we want to check if there's a segment in the array $$$t$$$ such that its left border is greater than $$$s$$$ (the last position where we made a replacement), the right border is $$$i$$$, and the sum is $$$0$$$. We can show that the sum on any segment ending in the $$$i$$$-th position is currently non-negative; so, we actually want to find the segment with the minimum sum. We can store a segment tree that, for every position $$$l$$$ from $$$s+1$$$ to $$$i$$$, maintains the sum on segment $$$[l, i]$$$; then changing an element is just performing the query "add on segment", and finding the minimum sum is just performing the query "minimum on segment". This allows us to get a solution with complexity of $$$O(n \log n)$$$.