مهرشاد یک میوه فروشی دارد که فقط پرتقال می‌فروشد. او پرتقال ها را در $q$ کیسه داخل انبار نگه‌داری می‌کند؛ این کیسه‌ها با اعداد $1$ تا $q$ شماره‌گذاری شده‌اند. درون کیسه‌ی $i$ام، $x_i$ پرتقال وجود دارد.

او امروز تصمیم گرفته که همه‌ی کیسه‌ها را جلوی مغازه داخل یک ردیف بچیند. برای این کار، در مرحله‌ی $i$ام کیسه‌ی $i$ام را برمی‌دارد و پشت $p_i$امین کیسه‌ی پرتقال می‌گذارد (اگر $p_i = i$ باشد، کیسه‌ی $i$ام جلوی تمامی کیسه‌های موجود در صف قرار می‌گیرد.) ؛ سپس تمام کیسه‌های جلوی آن را یک واحد به جلو هل می‌دهد. به طور مثال اگر $p_4 = 2$ باشد، پیش از مرحله‌ی ۴ام در صف ۳ کیسه قرار دارد. پس از این مرحله، کیسه‌ی شماره‌ی ۴ بین کیسه‌ی اول و دوم قرار می‌گیرد. همچنین اگر $p_4 = 4$ باشد، کیسه‌ی شماره‌ی ۴ جلوی تمام کیسه‌ها قرار می‌گیرد.

او این کار را آن قدر تکرار می‌کند تا کیسه های داخل انبار تمام شوند. مهرشاد بعد از هر عملیاتی که انجام می‌دهد، برایش سوال می‌شود که «طول بزرگ‌ترین زیردنباله‌ی اکیداً صعودی(LIS) صف کیسه‌ها چند است؟» امّا از آن جایی که او سخت درگیر کار و کاسبی‌ش است و وقت سر خاراندن هم ندارد، شما باید به سوالاتش پاسخ دهید.

یک دنباله مثل $b_1, b_2, b_3, \cdots, b_i$ زیردنباله‌ای از صف پرتقال ها است اگر و فقط اگر، بتوان با حذف تعدادی دلخواه از کیسه ها به ردیفی از کیسه‌ها رسید که تعداد پرتقال‌های درونشان به ترتیب برابر با دنباله‌ی $b$ باشد.

در خط اول ورودی$q$، تعداد کیسه‌های درون انبار می‌آید.

در $q$ خط بعدی در هر خط دو عدد $p_i$ و $x_i$ می‌آید که اولی نشان دهنده‌ی مکانی است که مهرشاد کیسه‌ی $i$ام را می‌گذارد و دومی برابر با تعداد پرتقال های درون آن هست.

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

• زیرمسئله اول (۲۰ نمره): $q \le 2000$
• زیرمسئله دوم (۸۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq p_i \leq i$
• $1 \le q \le 10^{6}$
• $\sum x_i \leq 10^6$
• $1\leq x_i \leq 10^6$

در مثال اول صف پرتقال ها به این ترتیب تغییر می‌کند:

• $\langle 7 \rangle$
• $\langle 7, 10 \rangle$
• $\langle 7, 11, 10 \rangle$
• $\langle 7, 8, 11, 10 \rangle$
• $\langle 7, 8, 11, 10, 10 \rangle$
• $\langle 2, 7, 8, 11, 10, 10 \rangle$

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