+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیرحسین یک زمین دارد که از $n$ بخش پشت سر هم تشکیل شده است. ارتفاع بخش $i$ام برابر $a_i$ است و آرایه‌ی $a$ یک جایگشت از اعداد $1$ تا $n$ است. به بخشی از زمین **چاله** می‌گوییم اگر ارتفاع آن از تمام بخش‌های مجاورش کمتر باشد. یعنی اگر یک بخش همسایه‌ای نداشته باشد این بخش حتما چاله خواهد بود، اگر فقط یک همسایه داشته باشد، کافی است از همان همسایه کوتاه‌تر باشد و اگر دو همسایه داشته باشد، باید از هر دوی آن‌ها کوتاه‌تر باشد. حالا امیرحسین روی هر بخش از زمین یک توپ دارد و می‌خواهد برای هر توپ بداند اگر آن را از همان بخش به یکی از دو جهت **چپ یا راست** قل بدهد، حداقل چقدر زمان لازم است تا توپ وارد یک چاله شود (ممکن است توپ با شروع حرکت در یک جهت به هیچ چاله ای نرسد، اما تضمین می‌شود هر توپ در دست‌کم یکی از دو جهت ممکن به یک چاله می‌رسد؛ مگر اینکه از ابتدا داخل چاله باشد که پاسخ آن صفر است)، در صورت قل دادن یک توپ به یک جهت تا زمانی که ارتفاع خانه فعلی توپ از خانه بعدی (در جهت قل خوردن) بیشتر باشد توپ به خانه بعدی قل می‌‌خورد و هر حرکت به بخش کناری **۱ واحد زمان** طول می‌کشد، توجه کنید که توپ پس از شروع حرکت تغییر جهت نمی‌دهد. برای هر بخش، حداقل زمان لازم برای اینکه توپ قرارگرفته روی آن بخش وارد یک چاله شود را پیدا کنید. # ورودی در خط اول عدد صحیح $n$ داده می‌شود.$$1 \le n \le 2*10^5$$ در خط دوم $n$ عدد صحیح داده می‌شود که عدد $i$م ارتفاع بخش‌ $i$م زمین را مشخص می‌کند.$$1 \le a_i \le n$$ آرایه $a$ یک جایگشت از اعداد $1$ تا $n$ است و ارتفاع هیچ دو بخشی با هم برابر نیست. # خروجی در یک خط، $n$ عدد چاپ کنید که عدد $i$ام آن برابر با حداقل زمان لازم برای رسیدن توپِ بخش $i$ به یک چاله باشد. # مثال ## ورودی نمونه ۱ ``` 7 2 3 6 7 4 1 5 ``` ## خروجی نمونه ۱ ``` 0 1 2 2 1 0 1 ```