سوال ۱

آقای مهندس قلکش را شکسته و با پول داخل آن یک جزیره خریده است. اما ظاهرا جزیره‌ را به او قالب کرده‌اند و جزیره‌ای که خریده هیچ زمین صافی ندارد و بیشتر به کوهستان شبیه است. سطح جزیره‌ی آقای مهندس را می‌توان به صورت یک خط شکسته در صفحه‌ی مختصات نشان داد. در واقع اگر ارتفاع نقطه‌های جزیره را $a_1, a_2, \cdots , a_n$ در نظر بگیریم، جزیره را می‌توان به صورت یک خط شکسته متشکل از نقاط $(0, 0), (1, a_1), (2, a_2), . . . , (n, a_n), (n + 1, 0)$ نمایش داد به طوری که نقاط متوالی با یک پاره‌خط راست به یک‌دیگر متصل‌اند.

هم‌چنین به خاطر جزر و مد دریا، سطح آب در طول زمان متفاوت است و با بالا آمدن سطح دریا سطح جزیره به چند قسمت تقسیم می‌شود.

توجه داشته باشید که یک نقطه از جزیره که دقیقا هم‌سطح آب است زیر سطح آب حساب می‌شود. یعنی اگر نوک قله‌ای هم‌سطح آب باشد، نوک قله یک قسمت جزیره حساب نمی‌شود و هم‌چنین اگر انتهای دره‌ای هم‌سطح آب باشد، دو طرف انتهای دره دو قسمت متفاوت حساب می‌شوند. برای مثال در شکل زیر جزیره سه قسمت دارد.

حال برنامه‌ای بنویسید که با گرفتن اطلاعات مربوط به جزیره، به درخواست‌های زیر پاسخ دهد:

• $x \ h$ ! : ارتفاع نقطه‌ی‌ $x‌$ام به $h‌$ تغییر می‌کند. حال پیدا کنید که بعد از این تغییر در طی بالا آمدن آب از سطح صفر تا بینهایت، جزیره حداکثر چند قسمت می‌شود؟
• $p$ ? : کمترین ارتفاع آبی که به ازای آن جزیره به دقیقا $p$ قسمت تقسیم می‌شود، چقدر است؟ در صورتی که هیچ‌گاه جزیره به دقیقا $p$ قسمت تقسیم نمی شود، مقدار  $−1$ را چاپ کنید.
• $h$ ~ : تعداد قسمت‌های جزیره در صورتی که ارتفاع آب دقیقن برابر $h$ باشد، چند تاست؟

• در سطر اول ورودی عدد طبیعی $n$، تعداد نقاط جزیره آمده است.
• در سطر بعد $n$ عدد طبیعی $a_1, a_2, \cdots , a_n$ آمده‌اند که ارتفاع نقاط جزیره را نشان می‌دهند.
• در سطر بعد نیز عدد طبیعی $q$، تعداد درخواست‌ها آمده‌است.
• در هر کدام از $q$ سطر بعدی نیز یک درخواست به یکی از سه شکل گفته‌شده در صورت سوال آمده‌است.
• $1 \leq n, q \leq 10^5$
• $1 \leq a_i \leq 10^9$
• $1 \leq x \leq n$ و $ 1\leq h \leq 10^9$
• $1 \leq p \leq n$
• $1 \leq h \leq 10^9$
• همه‌ $a_i$ها متمایزند و بعد از درخواست‌های ! نیز متمایز می‌مانند.

خروجی شامل $q$ سطر است که در سطر $i$ام آن پاسخ به $i$امین درخواست نوشته شده‌است.

• زیرمسئله اول (۱۰ نمره): $n, q \leq 2000$
• زیرمسئله دوم (۱۰ نمره): فقط درخواست نوع ~ داریم.
• زیرمسئله سوم (۲۵ نمره): فقط درخواست نوع ! و ~ داریم.
• زیرمسئله چهارم (۵۵ نمره): بدون محدودیت اضافی

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

ورودی نمونه اول مانند تصویر زیر است.

• سوال قبل