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 \leq n \leq 200000~).
• Dòng tiếp theo chứa ~n~ số nguyên ~c_1,...,c_n~ (~1 \leq c_i \leq 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 1

5
1 2 3 4 5

Example Output 1

4

Example Input 2

6
1 8 1 1 7 1

Example Output 2

3