EIU Programming Practices and Exams

Một hôm Beo nằm mơ thấy mình bị lạc vào xứ sở thần tiên và đang bị một con sói đuổi theo. Trước mặt Beo  là một con sông, trên sông có n hòn đá xếp thành một đường thẳng và trên hòn đá thứ n có một lối ra. Tuy nhiên những hòn đá này không phải là những hòn đá bình thường mà là những hòn đá phép thuật, mỗi hòn đá có một màu.

Khi di chuyển trên những hòn đá này Beo chỉ có thể:

* nhảy tới hòn đá trước mặt. Hoặc

* nhảy tới hòn đá gần nhất có cùng màu với hòn đá Beo đang đứng.

Beo đang đứng ở hòn đã thứ nhất. Giúp Beo tính số bước nhảy ít nhất để Beo có thể đến hòn đá thứ n.

Input

Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 200000).

Dòng tiếp theo chứa n số nguyên c1,...,cn  (1 ≤ ci ≤ 200000).. Tương ứng là màu của các viên đá.

Output

Số bước nhảy ít nhất Beo có thể đến hòn đá thứ n.

Example

Input:
5
1 2 3 4 5

Output:
4

Input:
6
1 8 1 1 7 1

Output:
3