چند موضوعی - 270B

یک سوال نسبتا نکته دار و متوسط رو به بالا به اسم چند موضوعی و با شماره ی 270B از سایت عظیم کدفورسس!

---

چند موضوعی - 270B

سپهر به سایت کدفوسس علاقه شدیدی داشت و هی صفحه رو ریفرش می کرد تا تغییری را در قسمت recent actions از دست نده!او دوست داره موضوعاتی رو بخونه که توی اون موضوعات پیام جدیدی باشه.

recent actions نشان دهنده ی n موضوع مختلف است که بر اساس زمان آخرین پیام در موضوع طبقه بندی شده اند.وقتی پیام جدید در موضوعی می آید، آن موضوع به اول لیست می آید.هیچ دو پیامی از موضوعات مختلف همزمان نمی آیند.

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

به سپهر کمک کنید که تعداد موضوعاتی رو پیدا کنه که قطعا پیام جدید دارند.موضوع x قطعا پیام جدید داره در صورتی که هیچ دنباله ای از موضوعات وجود نداشته باشه که هر دو شرایط زیر را داشته باشند.

1. موضوع x آپدیت نشده باشه (پیام جدیدی نداشته باشه).
2. ترتیب لیست از یک تا n تبدیل بشه به a₁, a₂, ..., a_n.

ورودی:

در خط اول عدد صحیح n که (1 ≤ n ≤ 10⁵) و در خط بعد n عدد صحیح a₁, a₂, ..., a_n که هر کدام از بزرگتر مساوی یک و کوچکتر مساوی n هستند که جایگاه قدیمیِ i امین موضوع در لیست جدید هستند.مطمئن باشید که همه ی a_i ها متمایز اند.

خروجی:

تعداد موضوعاتی رو چاپ کنید که مطمئن هستید دارای پیام جدید اند.

 

 

ورودی

5
5 2 1 3 4

خروجی

2

ورودی

3
1 2 3

خروجی

0

ورودی

4
4 3 2 1

خروجی

3

نکته:

در مثال اول موضوعات 2 و 5 قبل از موضوع 1 اند.برای همین این موضوعات مطمئناً باید پبام جدید داشته باشند.موضوعات 1 و 3 و 4 ممکن است پیام جدید نداشته باشند، اگر فقط 2 و 5 پیام جدید داشته باشند.

در مثال دوم ممکن است پیام جدیدی وجود نداشته باشد چون اصلا ترتیبشان تغییر نکرده است.

در مثال سوم فقط موضوع 1 می تواند پیام جدید نداشته باشد.

جواب: http://tny.cz/da677e74

---

اینم از کدفورسس که می خواستین! بازم می ذارم. :دی