+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + روز ۱ دوره ۳۰ ---------- مهرشاد یک میوه فروشی دارد که فقط پرتقال می‌فروشد. او پرتقال ها را در $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$ام را می‌گذارد و دومی برابر با تعداد پرتقال های درون آن هست. $$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$$ # خروجی به ازای هر عملیات مهرشاد، اندازه‌ی بزرگ‌ترین زیردنباله‌ی صعودی صف پرتقال‌ها را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۲۰ | $ q \le 2000 $ | | ۲ | ۸۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 6 1 7 2 10 2 11 2 8 4 10 1 2 ``` ## خروجی نمونه ۱ ``` 1 2 2 3 3 4 ``` ## ورودی نمونه ۲ ``` 4 1 3 2 1 1 1 2 2 ``` ## خروجی نمونه ۲ ``` 1 1 2 3 ```

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