المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۱۴:عملی:سوال ۳

نوار

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

شما این مقدار کمینه را برای $x$ حساب کنید.

ورودی

در سطر اول فایل ورودی، $n$ تعداد اعداد آمده و در $n$ سطر بعدی به ترتیب اعداد موجود در خانه‌های ۰ تا $n-1$ می‌آید.($1\leq n \leq 10^5$)

خروجی

در تنها سطر خروجی $x$‌را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۰/۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3
2
1
3
1

ابزار صفحه