Di chuyển

Cho mảng số nguyên \(a\) gồm \(n\) phần tử, đánh chỉ số từ \(0\) đến \(n-1\). Ban đầu bạn đứng ở vị trí \(0\). Trong mỗi bước, bạn được phép di chuyển:

• Sang trái: từ \(i\) sang \(i-1\) nếu \(i-1 \ge 0\);
• Sang phải: từ \(i\) sang \(i+1\) nếu \(i+1 < n\);
• Dịch chuyển theo giá trị bằng nhau: từ \(i\) sang bất kỳ \(j\) (\(j \ne i\)) sao cho \(a[j] = a[i]\).

Mục tiêu là tới vị trí \(n-1\) với số bước ít nhất.

Input

Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
Dòng tiếp theo chứa \(n\) số nguyên \(a_0, a_1, \ldots, a_{n-1}\) (\(|a_i| \le 10^9\)).

Output

In ra số bước ít nhất để đi từ vị trí \(0\) tới vị trí \(n-1\).

Scoring

• Subtask 1 (50 điểm): \(n \le 2000\).
• Subtask 2 (50 điểm): Không ràng buộc thêm, \(n \le 2 \cdot 10^5\).

Sample Input 1

10
100 -23 -23 404 100 23 23 23 3 404

Sample Output 1

3

Sample Input 2

8
7 6 9 6 9 6 9 7

Sample Output 2

1