+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بهراد $n$ مین در یک ردیف پیدا کرده است که مین $i$ام در مختصات $x_i$ محور اعداد قرار دارد. او که می‌خواهد محیط را مین‌زدایی کند، تصمیم گرفته همه مین‌ها را منفجر کند. برای انفجار هر مین باید نیرویی به آن وارد شود. اگر به یک مین به اندازه $k$ $(k \ge 1)$ نیرو وارد شود،‌ مین منفجر شده و به تمام مین‌هایی که در فاصله کمتر مساوی $k$ از آن مین قرار دارند نیز به اندازه $k$ نیرو وارد می‌کند (که باعث انفجار آن‌ها نیز می‌شود). هر بار بهراد می‌تواند نیرویی به یک مین وارد کند و کل نیرویی که مصرف می‌کند برابر است با جمع همه نیرو‌هایی که **مستقیما** به مین‌ها وارد کرده است. بهراد می‌خواهد بداند که حداقل چقدر نیرو لازم دارد تا همه مین‌ها را منفجر کند. # ورودی در خط اول ورودی عدد $n$، تعداد مین‌ها، آمده‌است. در خط دوم $n$ عدد آمده است که عدد $i$ام، $x_i$، مکان مین $i$ام را که عددی صحیح است نشان می‌دهد. $$1 \le n \le 3\times10^5$$ $$0 \le x_i \le 10^{18}$$ دنباله $x$ اکیدا صعودی است. # خروجی در تنها خط خروجی حداقل نیروی لازم برای منفجر کردن همه مین‌ها را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۲۵ | $1 \le n \le 2000$ | |۲| ۳۵ | $1 \le n \le 10^5, 0 \le x_i \le 2\times10^5$ | |۳| ۴۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 1 3 10 12 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 8 0 1 4 5 8 9 12 13 ``` ## خروجی نمونه ۲ ``` 3 ```

مین‌ها

محدودیت زمان: ۳ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

بهراد $n$ مین در یک ردیف پیدا کرده است که مین $i$ ام در مختصات $x_i$ محور اعداد قرار دارد. او که می‌خواهد محیط را مین‌زدایی کند، تصمیم گرفته همه مین‌ها را منفجر کند.

برای انفجار هر مین باید نیرویی به آن وارد شود. اگر به یک مین به اندازه $k$ $(k \ge 1)$ نیرو وارد شود،‌ مین منفجر شده و به تمام مین‌هایی که در فاصله کمتر مساوی $k$ از آن مین قرار دارند نیز به اندازه $k$ نیرو وارد می‌کند (که باعث انفجار آن‌ها نیز می‌شود).

هر بار بهراد می‌تواند نیرویی به یک مین وارد کند و کل نیرویی که مصرف می‌کند برابر است با جمع همه نیرو‌هایی که مستقیما به مین‌ها وارد کرده است.

بهراد می‌خواهد بداند که حداقل چقدر نیرو لازم دارد تا همه مین‌ها را منفجر کند.

ورودی🔗

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

در خط دوم $n$ عدد آمده است که عدد $i$ ام، $x_i$ ، مکان مین $i$ ام را که عددی صحیح است نشان می‌دهد.

$1 \le n \le 3\times10^5$ $0 \le x_i \le 10^{18}$

دنباله $x$ اکیدا صعودی است.

خروجی🔗

در تنها خط خروجی حداقل نیروی لازم برای منفجر کردن همه مین‌ها را چاپ کنید.

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۲۵	$1 \le n \le 2000$
۲	۳۵	$1 \le n \le 10^5, 0 \le x_i \le 2\times10^5$
۳	۴۰	بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

4
1 3 10 12

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

8
0 1 4 5 8 9 12 13

خروجی نمونه ۲🔗

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- السا و مهرسا می‌خواهند میوه‌ها را برای مراسم آماده کنند. السا وظیفه شستن میوه‌ها را بر‌عهده دارد و مهرسا باید میوه‌ها را در ظرف قرار دهد. $n$ میوه داریم که در پشته یک قرار دارند و میوه‌ها از سر پشته تا ته پشته از $1$ تا $n$ شماره گذاری شده‌اند. هر بار السا می‌تواند یک میوه از سر پشته‌ی یک (در صورتی که خالی نباشد) بردارد و بشورد سپس در پشته‌ی دو قرار دهد. مهرسا نیز می‌تواند یک میوه از سر پشته‌ی دو (در صورتی که خالی نباشد) برداشته و سپس در ظرفی که هم اکنون جلوی او قرار دارد بگذارد یا ظرفی که جلویش هست را کنار گذاشته و از ظرف خالی دیگری استفاده کند (مهرسا دیگر نمی‌تواند از ظرفی که کنار گذاشته است استفاده کند). هر ظرف تنها تحمل $k$ کیلوگرم میوه را دارد و جمع وزن میوه‌هایی که مهرسا در یک ظرف می‌گذارد نباید از $k$ کیلوگرم بیشتر باشد. آنها می‌خواهند طوری این میوه‌ها را در ظرف‌ها قرار دهند که کمترین تعداد ظرف ممکن استفاده شود. این کمینه را برای آن‌ها بیابید. # ورودی در خط اول ورودی عدد $n$، تعداد میوه‌ها، و $k$ حداکثر تحمل یک ظرف، آمده است. در خط دوم $n$ عدد آمده است که عدد $i$ام، $w_i$، وزن میوه $i$ام را نشان می‌دهد. $$1 \le n, k \le 70$$ $$1 \le w_i \le k$$ # خروجی در تنها خط خروجی حداقل تعداد ظرف لازم برای اینکه میوه‌ها در ظرف‌ها قرار داده شوند را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۲ | $k = 1$| |۲| ۸ | $k \le 2$ | |۳| ۱۷ |$1 \le n \le 12$ | |۴| ۴۴ | $1 \le n, k \le 30$ | |۵| ۲۹ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 6 2 1 2 2 1 1 2 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 6 4 3 2 3 1 2 3 ``` ## خروجی نمونه ۲ ``` 4 ```

رویه

محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

السا و مهرسا می‌خواهند میوه‌ها را برای مراسم آماده کنند. السا وظیفه شستن میوه‌ها را بر‌عهده دارد و مهرسا باید میوه‌ها را در ظرف قرار دهد. $n$ میوه داریم که در پشته یک قرار دارند و میوه‌ها از سر پشته تا ته پشته از $1$ تا $n$ شماره گذاری شده‌اند.

هر بار السا می‌تواند یک میوه از سر پشته‌ی یک (در صورتی که خالی نباشد) بردارد و بشورد سپس در پشته‌ی دو قرار دهد.

مهرسا نیز می‌تواند یک میوه از سر پشته‌ی دو (در صورتی که خالی نباشد) برداشته و سپس در ظرفی که هم اکنون جلوی او قرار دارد بگذارد یا ظرفی که جلویش هست را کنار گذاشته و از ظرف خالی دیگری استفاده کند (مهرسا دیگر نمی‌تواند از ظرفی که کنار گذاشته است استفاده کند).

هر ظرف تنها تحمل $k$ کیلوگرم میوه را دارد و جمع وزن میوه‌هایی که مهرسا در یک ظرف می‌گذارد نباید از $k$ کیلوگرم بیشتر باشد.

آنها می‌خواهند طوری این میوه‌ها را در ظرف‌ها قرار دهند که کمترین تعداد ظرف ممکن استفاده شود. این کمینه را برای آن‌ها بیابید.

ورودی🔗

در خط اول ورودی عدد $n$ ، تعداد میوه‌ها، و $k$ حداکثر تحمل یک ظرف، آمده است.

در خط دوم $n$ عدد آمده است که عدد $i$ ام، $w_i$ ، وزن میوه $i$ ام را نشان می‌دهد. $1 \le n, k \le 70$ $1 \le w_i \le k$

خروجی🔗

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

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۲	$k = 1$
۲	۸	$k \le 2$
۳	۱۷	$1 \le n \le 12$
۴	۴۴	$1 \le n, k \le 30$
۵	۲۹	بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

6 2
1 2 2 1 1 2

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

6 4
3 2 3 1 2 3

خروجی نمونه ۲🔗

+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- زمان زیادی تا کانتست نمانده بود و آنیتا دیگر حوصله نداشت برای سوالات داستان بسازد، برای همین او از شما می‌خواهد که سوال زیر را حل کنید. یک دنباله به طول $n$ از اعداد $1$ تا $n$ داده شده است و هر بار یکی از دو نوع درخواست زیر داده می‌شود: نوع اول: یک بازه از دنباله و دو عدد $x$ و $y$ داده می‌شود و تمام عنصرهای $x$ آن بازه به $y$ تبدیل می‌شوند. نوع دوم :‌ یک بازه از دنباله و یک عدد $k$ داده می‌شود و می‌پرسد «اگر تمام بازه را از کوچک به بزرگ مرتب کنیم، عنصر $k$ام کدام است؟». # ورودی در خط اول ورودی دو عدد $n$، تعداد اعداد دنباله و $m$، تعداد درخواست‌ها، آمده‌است. در خط دوم $n$ عدد آمده است که عدد $i$ام، $a_i$، عدد $i$ام دنباله را نشان می‌دهد. در $m$ خط بعدی، در هر خط یک درخواست به یکی از دو شکل زیر آمده‌است: هر عدد $x$ در بازه $l$ تا $r$ از دنباله (شامل خود آن‌ها) به $y$ تبدیل می‌شود. اگر بازه $l$ تا $r$ از دنباله (شامل خود آن‌ها) را از کوچک به بزرگ مرتب کنیم، $k$امین عنصر آن را چاپ کنید. $$1 \le n, m \le 10^5$$ $$1 \le a_i \le n$$ $$1 \le l \le r \le n$$ $$1 \le x, y \le n$$ $$1 \le k \le r - l + 1$$ # خروجی به ازای هر درخواست نوع دوم عدد خواسته‌ شده را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۹ | $1 \le n, m \le 1000$ | |۲| ۲۳ | همه درخواست ها از نوع دوم هستند | |۳| ۶۸ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 7 4 1 2 2 7 3 4 4 1 3 5 2 3 2 1 5 4 1 1 5 7 2 2 4 7 3 ``` ## خروجی نمونه ۱ ``` 3 4 ``` درخواست اول از نوع یک است که در بازه ۳ تا ۵ تمام اعداد ۲ را به ۳ تبدیل میکند. درخواست دوم چهارمین عدد در حالت مرتب شده ی بازه ۱ تا ۵ را میخواهد. اعداد بازه ۱ تا ۵ به ترتیب ۱ ۲ ۳ ۳ ۷ اند. درخواست سوم اعداد بازی ۱ تا ۵ که برابر با ۷ اند را به ۲ تغییر میدهد. و در نهایت درخواست آخر سومین عدد در حالت مرتب شده در بازه ۴ تا ۷ را میخواهد که اعداد این بازه ۲ ۳ ۴ ۴ اند.

توکار

محدودیت زمان: ۶ ثانیه
محدودیت حافظه: ۵۱۲ مگابایت

زمان زیادی تا کانتست نمانده بود و آنیتا دیگر حوصله نداشت برای سوالات داستان بسازد، برای همین او از شما می‌خواهد که سوال زیر را حل کنید.

یک دنباله به طول $n$ از اعداد $1$ تا $n$ داده شده است و هر بار یکی از دو نوع درخواست زیر داده می‌شود:

نوع اول: یک بازه از دنباله و دو عدد $x$ و $y$ داده می‌شود و تمام عنصرهای $x$ آن بازه به $y$ تبدیل می‌شوند.

نوع دوم :‌ یک بازه از دنباله و یک عدد $k$ داده می‌شود و می‌پرسد «اگر تمام بازه را از کوچک به بزرگ مرتب کنیم، عنصر $k$ ام کدام است؟».

ورودی🔗

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

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

در $m$ خط بعدی، در هر خط یک درخواست به یکی از دو شکل زیر آمده‌است:

هر عدد $x$ در بازه $l$ تا $r$ از دنباله (شامل خود آن‌ها) به $y$ تبدیل می‌شود.

اگر بازه $l$ تا $r$ از دنباله (شامل خود آن‌ها) را از کوچک به بزرگ مرتب کنیم، $k$ امین عنصر آن را چاپ کنید.

$1 \le n, m \le 10^5$

$1 \le a_i \le n$

$1 \le l \le r \le n$

$1 \le x, y \le n$

$1 \le k \le r - l + 1$

خروجی🔗

به ازای هر درخواست نوع دوم عدد خواسته‌ شده را چاپ کنید.

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۹	$1 \le n, m \le 1000$
۲	۲۳	همه درخواست ها از نوع دوم هستند
۳	۶۸	بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

7 4
1 2 2 7 3 4 4
1 3 5 2 3 
2 1 5 4
1 1 5 7 2 
2 4 7 3

خروجی نمونه ۱🔗

3
4

درخواست اول از نوع یک است که در بازه ۳ تا ۵ تمام اعداد ۲ را به ۳ تبدیل میکند.

درخواست دوم چهارمین عدد در حالت مرتب شده ی بازه ۱ تا ۵ را میخواهد. اعداد بازه ۱ تا ۵ به ترتیب ۱ ۲ ۳ ۳ ۷ اند.

درخواست سوم اعداد بازی ۱ تا ۵ که برابر با ۷ اند را به ۲ تغییر میدهد.

و در نهایت درخواست آخر سومین عدد در حالت مرتب شده در بازه ۴ تا ۷ را میخواهد که اعداد این بازه ۲ ۳ ۴ ۴ اند.