- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
فامیل دور که در کار در فعالیت دارد، در یک جدول مربع شکل درگیر پیدا کردن بچه فامیل شده است. فامیل در خانه تقاطع سطر اول و ستون اول جدول قرار دارد، غافل از اینکه بچه فامیل به خانه تقاطع سطر آخر و ستون آخر جدول رفته است. بچه فامیل در مسیر خود تعدادی رد پا هم به جا گذاشته است. به طوری که در هر سطر و هر ستون دقیقا روی یک خانه ردپا دیده میشود. فامیل به دنبال بچه فامیل، در هر حرکت میتواند به یکی از چهار خانه مجاور ضلعی خانه فعلی اش برود. همچنین اگر در هشت خانه مجاور راسی اش ردپایی ببیند به امید پیدا کردن بچه فامیل میتواند در یک حرکت به آن خانه هم برود. فامیل که از پیدا کردن بچه فامیل ناامید شده با وجود شما افق های روشنی پیش روی خودش میبیند. برای اینکه فامیل را ناامید نکنید کمترین تعداد حرکتی که میتواند فامیل را به بچه فامیل برساند، به او اعلام کنید.
ورودی
در سطر اول ورودی عدد \(n\) میآید که برابر با تعداد سطرها و ستونهای جدول است.
در سطر بعدی \(n\) عدد متفاوت بین ۱ تا \(n\) میآید که \(i\)مین آنها \(p_i\) است و به معنای وجود ردپا در خانه تقاطع سطر \(p_i\) و ستون \(i\) است. \[1 \le n \le 300\ 000\]
\[1 \le p_i \le n\]
خروجی
در تنها سطر خروجی کمترین تعداد حرکتی که میتواند فامیل را به بچه فامیل برساند باید چاپ شود.
مثال
ورودی نمونه ۱
5
4 3 2 5 1
خروجی نمونه ۱
6
ورودی نمونه ۲
4
4 2 1 3
خروجی نمونه ۲
4