یک نوار داریم که از یک سمت نامتناهی است و خانههای آن را با شمارههای ۱،۰ و … شمارهگذاری کردهایم. در n خانهی ابتدای این نوار، اعداد ۱ تا n قرار گرفتهاند. در یک حرکت میتوانیم یک عدد را انتخاب کرده و آن را از مکان فعلیاش به یک خانهی خالی در سمت راست منتقل کنیم. بالطبع پس از این حرکت خانهی اولی خالی و خانهی دوم پر میشود. هدف ما این است که این اعداد را به صورت مرتب شده در n خانهی مجاور نوار داشته باشیم. بنا به دلایل فنی از ما خواسته شده که کمینهی x را پیدا کنیم که بتوان با تعدادی حرکت اعداد را به خانههای x تا x+n−1 ببریم و عدد موجود در خانهی x،۱ و محتوای خانهی x+n−1 نیز n باشد.
شما این مقدار کمینه را برای x حساب کنید.
در سطر اول فایل ورودی، n تعداد اعداد آمده و در n سطر بعدی به ترتیب اعداد موجود در خانههای ۰ تا n−1 میآید.(1≤n≤105)
در تنها سطر خروجی xرا بنویسید.