Саяхан л гэхэд Майк шалгалт болон тэмцээнд бэлдээд маш завгүй байсан. Харин одоо тэр хотыг ажиглаад бага зэрэг даарч эхэлж байна.

Хот $1$-c $n$ хүртэл дугаарлагдсан $n$ уулзвараас бүрдэнэ. Майк $1$ уулзвар дээр байрлах өөрийн байшингаас эхлэн алхах ба хэд хэдэн уулзвараар алхана. $i$ уулзвараас $j$ уулзвар хүрэхэд $|i - j|$ нэгж энерги хэрэгтэй. $p_{1} = 1, p_{2}, ..., p_{k}$ уулзваруудаар зочлоход Майкийн зарцуулах нийт энерги нь нэгж энергитэй тэнцүү байна.

Мэдээж ямар ч товч зам байхгүй бол алхах нь уйтгартай ажил. Товч зам гэдэг нь Майк нэг уулзвараас өөр уулзварруу зөвхөн $1$ нэгж энерги ашиглан хүрч болох тусгай зам юм. Майкийн хотод яг $n$ товч зам байдаг ба тэдний $i$ дэх нь $i$-р уулзвараас $a_{i}$ ($i ≤ a_{i} ≤ a_{i + 1}$) уулзварруу явах боломж (гэхдээ эсрэг зүгт биш) олгох бөгөөд уулзвар бүрээс эхэлсэн яг нэг товч зам байна. Тодорхой хэлбэл хэрвээ Майк $p_{1} = 1, p_{2}, ..., p_{k}$ дарааллыг сонговол $1 ≤ i < k$ бүрийн хувьд $p_{i + 1} = a_{p_{i}}$ ба $a_{p_{i}} ≠ p_{i}$ хангагдах ба Майк $p_{i}$ уулзвараас $p_{i + 1}$ уулзварруу алхахдаа $|p_{i} - p_{i + 1}|$ нэгж энергийн оронд зөвхөн $1$ нэгж энерги зарцуулна. Жишээлбэл хэрвээ Майк $p_{1} = 1, p_{2} = a_{p_{1}}, p_{3} = a_{p_{2}}, ..., p_{k} = a_{p_{k - 1}}$ дарааллыг сонговол эдгээрээр алхахдаа нийт яг $k - 1$ нэгж энерги зарцуулна.

Майк адал явдалд гарахаасаа өмнө таныг түүний гэрээс уулзвар бүррүү очиход шаардлагатай энергийн хамгийн бага хэмжээг олохыг хүсч байна. Тодорхой хэлбэл $1 ≤ i ≤ n$ бүрийн хувьд Майк $p_{1} = 1, p_{2}, ..., p_{k} = i$ дарааллын боломжит хамгийн бага нийт энергийн хэмжээг мэдэхийг хүсч байна.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ $(1 ≤ n ≤ 200 000)$ байх буюу Майкийн хот дахь уулзваруудын тоо.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ $(i ≤ a_{i} ≤ n$, байх ба Майкийн хот дахь товч замуудыг тодорхойлно. Товч замууд нь эсрэг зүгт ($a_{i}$-с $i$-рүү) явахыг зөвшөөрөхгүй .

Гаралт

Нэг мөрөнд $n$ бүхэл тоо $m_{1}, m_{2}, ..., m_{n}$ байх ба энд $m_{i}$ нь $1$ уулзвараас $i$ уулзвар хүрэхэд шаардлагатай нийт энергийн хамгийн бага хэмжээг заана.

Эхний жишээн дээр шаардлагатай дарааллууд нь:

$1: 1$; $m_{1} = 0$;

$2: 1, 2$; $m_{2} = 1$;

$3: 1, 3$; $m_{3} = |3 - 1| = 2$.

Хоёр дахь жишээн дээр дурын $1 < i$ уулзварын хувьд дараалал нь үргэлж $1, i$ ба $m_{i} = |1 - i|$ байна.

Гурав дахь жишээн дээр дараах уулзваруудын дарааллыг авч үзье:

$1: 1$; $m_{1} = 0$;

$2: 1, 2$; $m_{2} = |2 - 1| = 1$;

$3: 1, 4, 3$; $m_{3} = 1 + |4 - 3| = 2$;

$4: 1, 4$; $m_{4} = 1$;

$5: 1, 4, 5$; $m_{5} = 1 + |4 - 5| = 2$;

$6: 1, 4, 6$; $m_{6} = 1 + |4 - 6| = 3$;

$7: 1, 4, 5, 7$; $m_{7} = 1 + |4 - 5| + 1 = 3$.