باب گارسون رستوران پیتزا گرد است، رستورانی که انواع مختلف پیتزا را عرضه می‌کند. به طور سنتی، همه‌ی میزهای پیتزا گرد به صورت گرد، با اندازه‌های مختلف هستند. هرگاه گروهی از مشتریان وارد رستوران می‌شوند، باب به آن‌ها برای پیدا کردن یک میز با اندازه‌ی متناسب کمک کرده و سفارش آن‌ها را به صورت تعداد تقاضا برای هر پیتزا یادداشت می‌کند. باب هم‌چنین وظیفه‌ی قرار دادن پیتزاها روی میز را به عهده دارد، به صورتی که هر مشتری پیتزایی که سفارش داده را دریافت کند.

متاسفانه، باب فراموش‌کار است و نمی‌تواند به خاطر بسپارد که هر مشتری کدام نوع پیتزا را سفارش داده است. در نتیجه، در اغلب مواقع او پیتزاها را به ترتیب اشتباهی روی میز قرار می‌دهد. با این وجود، مشتریان با یکدیگر هم‌کاری کرده و طی چند نوبت پیتزاها را به مشتریان صحیح می‌رسانند. در هر نوبت، هر مشتری می‌تواند یک پیتزا را که مقابل وی قرار دارد را با دست چپ برداشته و به مشتری سمت چپ خود بدهد، یا می‌تواند یک پیتزا با دست راست خود برداشته و به مشتری سمت راست خود بدهد. یک مشتری در یک نوبت می‌تواند به طور هم‌زمان از هر دو دست خود استفاده کرده تا ۲ پیتزا را به دو مشتری مجاور خود برساند. البته محدودیت فضایی موجب می‌شود که مقابل هر مشتری حداکثر ۵ پیتزا می‌تواند قرار بگیرد. پس یک مشتری تنها در صورتی می‌تواند یک پیتزا را مقابل مشتری مجاور خود بگذارد که فضای کافی مقابل آن مشتری وجود داشته باشد.

با در نظر گرفتن این محدودیت‌ها، برای هر گروه از مشتریان شیوه‌های مختلفی برای رساندن هر پیتزا به متقضیان مربوطه وجود دارد. ما می‌خواهیم بدانیم حداقل تعداد نوبت‌ها برای رساندن پیتزاها چند است. فرض کنید که این کار همواره ممکن باشد، یعنی تعداد پیتزاها از هر نوع با تعداد متقاضیان آن نوع برابر باشد. به عنوان مثال، در شکل زیر، گروهی از ۶ مشتری ردور یک میز گرد نشسته اند، روی هر مشتری برچسبی وجود دارد که نوع پیتزایی که سفارش داده را مشخص می‌کند. اعدادی که روی هر پیتزا وجود دارد نوع آن پیتزا را مشخص می‌کنند. همان‌گونه که مشخص است در ۲ نوبت می‌توان پیتزاها را به متقاضیان خود رساند. با این وجود، امکان انجام این کار در یک نوبت وجود ندارد، چرا که پیتزای نوع ۲ حداقل ۲ نوبت برای رسیدن به مقصد نیاز دارد.

برنامه‌ای بنویسید که حداقل تعداد نوبت‌هایی که لازم است تا همه‌ی پیتزاها به مشتریان صحیح خود برسند را پیدا کند. شیوه‌ی دقیق انجام این کار برای ما اهمیت ندارد. صرفا می‌خواهیم بدانیم حداقل تعداد نوبت‌ها چقدر است.

• ورودی از چندین سناریو تشکیل شده است. در خط اول هر سناریو یک عدد صحیح $n$ قرار گرفته، که تعداد مشتریان حاضر در گروه را مشخص می‌کند $(1\leq n\leq 1000)$. فرض کنید که مشتریان با شماره‌های از $1$ تا $n$ شماره‌گذاری شده و به ترتیب پادساعت‌گرد دور یک میز با اندازه‌ی $n$ نشسته‌اند، به گونه‌ای که مشتری شماره‌ی $1$ مجاور مشتری $n$ باشد.
• در $n$ خط بعدی (شماره‌گذاری شده از $1$ تا $n$) سفارش مشتریان و نحوه‌ی چینش پیتزا‌ها روی میز مشخص شده است. در خط $i$، دو عدد صحیح $a_i$ و $b_i$ قرار گرفته که در بازه‌ی $[1,n]$ هستند و با یک فاصله از یکدیگر جدا شده‌اند، که $a_i$ مشخص کننده‌ی نوع پیتزای سفارش داده شده توسط مشتری $i$ است و $b_i$ مشخص کننده‌ی نوع پیتزایی است که باب در مقابل وی قرار داده است. دنباله‌ی $b_i$ها در واقع جایگشتی از دنباله‌ی $a_i$ها می‌باشد.
• ورودی با یک خط حاوی $"0"$ خاتمه می‌یابد.

در خروجی، به ازای هر سناریو، تنها یک عدد ناصحیح $m$ را بنویسید، که حداقل تعداد نوبت های مورد نیاز برای جابه‌جا کردن پیتزاها در آن سناریو باشد. اگر در یک سناریو پیتزاها در ابتدا به ترتیب درستی قرار گرفته‌اند، شما باید عدد $0$ را در آن خط از خروجی چاپ کنید.

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

• سوال بعد
• سوال قبل