U آکاکی یک دسته از n کارت است. روی هر کارت دقیقاً یک عدد صحیح از 1 تا 100 000 نوشته شده است. این امکان وجود دارد که روی برخی از کارت ها همان اعداد نوشته شده باشد.
آکاکی تصمیم گرفت تمام کارت های موجود در عرشه را مرتب کند. برای این کار به نوبت یک کارت بالای عرشه را برمی دارد و اگر عددی که روی آن نوشته شده با کمترین تعداد در بین اعداد باقی مانده در عرشه برابر باشد، این کارت را کنار می گذارد. در غیر این صورت آکاکی این کارت را در پایین عرشه قرار می دهد و کارت بعدی را از بالای عرشه می کشد. این فرآیند زمانی به پایان می رسد که هیچ کارتی در عرشه باقی نماند. می‌توانیم فرض کنیم که آکاکی در هر زمانی حداقل تعداد نوشته شده روی برخی از کارت‌های باقی‌مانده در عرشه را می‌داند، اما نمی‌داند این کارت (یا کارت‌ها) در کجای عرشه قرار دارد.
وظیفه شما تعیین تعداد کل دفعاتی است که آکاکی از روی عرشه به کارت بالایی نگاه می کند.
ورودی
خط اول با یک عدد صحیح مثبت n دنبال می شود (1 ≤ n ≤ 100 000) — تعداد کارت های موجود در عرشه.
خط دوم شامل دنباله ای از n عدد صحیح مثبت a
1, a
2, ..., a
n ( 1 ≤ a
i ≤ 100 000)، که در آن a
i برابر است با عددی که روی iمین کارت بالایی از عرشه.< /div>
خروجی
تعداد کل دفعاتی که آکاکی به کارت بالای عرشه نگاه می کند را چاپ کنید.
<بدن>
|
وارد کنید |
خروجی |
|
4
6 3 1 2
|
7 |
1
1000
|
1 |
7
3 3 3 3 3 3 3
|
7 |
یادداشت
در مثال اول، آکاکی ابتدا به کارت با شماره 6 نگاه می کند، آن را در پایین عرشه قرار می دهد، سپس کارت با شماره 3، همچنین آن را در پایین عرشه قرار می دهد و سپس کارت با شماره 1. او کارت با شماره 1 را کنار می گذارد، زیرا حاوی حداقل تعداد باقی مانده در عرشه است. پس از آن، کارت های موجود در عرشه به ترتیب [2, 6, 3] از بالا به پایین قرار می گیرند. پس از آن آکاکی به کارت بالایی با شماره 2 نگاه می کند و آن را کنار می گذارد. پس از آن، کارت های موجود در عرشه به ترتیب [6, 3] از بالا به پایین قرار می گیرند. سپس آکاکی به کارت با شماره 6 نگاه می کند، آن را در پایین عرشه قرار می دهد و سپس کارت شماره 3 را که آن را کنار می گذارد. پس از آن یک کارت با شماره 6 در عرشه باقی می ماند که آکاکی آن را نگاه می کند و کنار می گذارد. بنابراین، آکاکی به 7 کارت نگاه می کند.
(ج) کورباتوف ای.، 2018