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

---

آقای مهندس قلکش را شکسته و با پول داخل آن یک جزیره خریده است. اما ظاهرن جزیره‌ را به او قالب کرده‌اند و جزیره‌ای که خریده هیچ زمین صافی ندارد و بیشتر به کوهستان شبیه است. سطح جزیره‌ی آقای مهندس را می‌توان به صورت یک خط شکسته در صفحه‌ی مختصات نشان داد. در واقع اگر ارتفاع نقطه‌های جزیره را $a_{1}, a_{2}, ..., 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, ..., a_n$ آمده‌اند که ارتفاع نقاط جزیره را نشان می‌دهند.

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

در هر کدام از $q$ سطر بعدی نیز یک درخواست به یکی از سه شکل گفته‌شده در صورت سوال آمده‌است.

$$1\leq n, q \leq 100\ 000$$ $$1\leq h, a_i\leq 10^9$$ $$1\leq p, x \leq n$$

• همه‌ $a_i$ها متمایزند و بعد از درخواست‌های ! نیز متمایز می‌مانند.

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۰	$ n,q \le 2\ 000 $
۲	۱۰	فقط درخواست نوع ~ داریم.
۳	۴۰	فقط درخواست نوع ! و ~ داریم.
۴	۴۰	بدون محدودیت اضافی

مثال

ورودی نمونه

7
8 6 7 3 4 2 5
14
! 4 1
! 4 3
~ 4
~ 3
~ 2
~ 1
? 3
? 2
? 1
! 5 9
! 7 10
? 4
? 3
? 2

خروجی نمونه

3
3
2
3
2
1
3
2
0
3
4
6
3
2

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون هفتم - ۱۳۹۳/۰۶/۱۹