给定一个长度为 $n$ 的序列 $a$，然后给 $m$ 次询问。

定义一次行走为从 $i$ 可以走到 $i+1$ 或 $i-1$,但要求是 $a_{i}$ 与 $a_{i-1}$ 或 $a_{i+1}$相同，花费 1 代价。然后你可以用魔法把你目前所在的位置修改为任意一个数，也需要花费 1 代价。

然后每次询问 $l,r$ 表示从 l 走到 r 需要的最小代价，其中询问之间互不影响，存在l>r

1<=n,m<=1e6,1<=a[i]<=n