+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دزد با مهارت، باید بتواند خوب تمرکز کند. متاسفانه دزد با وجود تمام شایستگی‌هایش موفق نشد که از سد پلیس‌ها رد شود و به طبقه‌ی آخر برود. بنابراین او یک راه دیگر را برای رسیدن به طبقه‌ی آخر انتخاب کرده است. او می‌خواهد با استفاده از تمرکز ذهنی، به پرواز در آمده و به طبقه‌ی آخر برود. اما متاسفانه مسئله‌ای بدجور فکرش را مشغول کرده و به او اجازه‌ی تمرکز نمی‌دهد. او از شما می‌خواهد که این مسئله را برایش حل نمایید تا فکرش آزاد شود. مسئله این است: اعداد یک تا $n$ بدون تکرار و به ترتیب دلخواه در یک ردیف نوشته‌ شده‌اند. به این ردیف به ترتیب دلخواه از اعداد، جایگشت می‌گوییم. برای مثال 5،6،4،1،3،2 یک جایگشت شش تایی است. پس ما یک جایگشت داریم. حالا از روی این جایگشت بدین گونه یک گراف می‌سازیم: اگر جایگشت را بصورت $p_1, p_2, ..., p_n$ نشان دهیم و راس های گراف ما با اعداد ۱ تا $n$ شماره گذاری شده باشند، یالی بین راس شماره $i$ و راس شماره $j$ وجود دارد اگر و تنها اگر $i < j$ و $p_i > p_j$. برای مثال اگر جایگشت ما 2،3،1 باشد، در گراف متناظر، راس شماره‌ی سه به دو راس دیگر متصل است ولی راس شماره‌ی دو به راس شماره‌ی یک متصل نیست. حالا سوال این است که این گراف چند مولفه‌ی همبندی دارد. (برای توضیحات بیشتر راجع به گراف و مولفه همبندی، [اینجا](https://fa.wikipedia.org/wiki/%D9%85%D8%A4%D9%84%D9%81%D9%87_%D9%87%D9%85%D8%A8%D9%86%D8%AF%DB%8C) را ببینید.) # ورودی در سطر اول ورودی $n$ آمده است که نمایانگر تعداد اعداد در جایگشت است. در سطر بعدی $n$ عدد آمده است که جایگشت را نشان می‌دهند. $i$مین عدد از این اعداد نمایانگر $p_i$ است. این اعداد، عددهای 1 تا $n$ هستند که به ترتیب دلخواه کنار هم چیده شده‌اند و هیچ عددی در این سطر دوبار نیامده است. $$ 1 \le n \le 1\ 000\ 000 $$ # خروجی در تنها سطر خروجی تعداد مولفه‌های همبندی گراف ساخته شده با جایگشت را خروجی دهید. # مثال ## ورودی نمونه ``` 6 3 2 4 1 6 5 ``` ## خروجی نمونه ``` 2 ``` توضیح: یال‌ها در گراف ساخته شده بین راس‌های زیر هستند: یک و دو، چهار و یک، دو و چهار، سه و چهار و پنج و شش. که باعث به وجود آمدن دو مولفه همبندی می‌شود که مولفه‌ی اول شامل راس‌های شماره‌ی 1 و 2 و 3 و 4 و مولفه‌ی دیگر شامل راس‌های 5 و 6 می‌باشد.

حل سؤال در بانک سؤالات