You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

走廊是只有一行地砖的直走廊。上面一共有 n 个格子，每个格子都被小度给予了一个数字 a_i 来表示它的种类。

小度现在站在 1 号格子，想要去到 n 号格子。小度可以正向或反向移动到相邻的格子，每次需要花费 1 的体力。

同时小度还有瞬移的能力 ， 其可以花费 1 的体力来瞬移到与当前格子种类相同的格子上 ， 只能瞬移到在当前格子后的第一个种类相同的格子上 ， 且不能反向瞬移到上一个种类相同的格子上。

小度想知道，到达 n 号格子需要花费的最小体力是多少。

Format

Input

第一行一个整数 n表示走廊上一共有 n 个格子。 1 ≤ n ≤ 2x10⁵ , 0 ≤ a_i ≤ 1x10⁶ ； 第二行 n 个整数，为自然数 a_i , 表示第 i 号格子的亮度。

Output

一行，一个整数 cost 表示花费的最小体力。

Samples

6
0 1 2 3 1 5

3

Limitation

1s, 1024KiB for each test case.