• محدودیت زمان: ۱.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران

---

جمشید از جایگشت‌ها بدش می‌آید و یک جایگشت به طول $n$ دارد که می‌خواهد طی تعدادی مرحله آن را پاک کند.

جمشید در هر مرحله می‌تواند یکی از اعداد جایگشت مانند $p_i$ که هنوز پاک نشده را انتخاب و خود آن عدد و تمام اعداد کوچکتر سمت راست و یا تمام اعداد کوچکتر سمت چپ آن عدد را پاک کند. با انجام این کار جمشید به میزان $b_i$ خسته می‌شود. دقت کنید که اعدادی که پاک نشده‌اند به یکدیگر می‌چسبند.

برای مثال اگر در جایگشت $p = \langle 1, 3, 4, 2, 5 \rangle$ با دنباله $b = \langle 1, 2, 3, 4, 5 \rangle$ عدد $p_2 = 3$ را انتخاب کنیم و تمام اعداد کوچکتر سمت راست آن را پاک کنیم، به جایگشت $p = \langle 1, 4, 5 \rangle$ با دنباله $b = \langle 1, 3, 5 \rangle$ می‌رسیم.

جمشید می‌خواهد پس از پاک کردن جایگشت فوتبال بازی کند پس می‌خواهد با کمترین میزان خستگی ممکن کل جایگشت را پاک کند.

مقدارهای $b_i$ در جایگشت جمشید $q$ بار تغییر می‌کنند و در هر بار تغییر یکی از مقادیر $b_i$ عوض می‌شود.

به جمشید کمک کنید تا کمترین میزان خستگی ممکن برای حذف کل جایگشت قبل از تمام تغییرات و پس از هر تغییر را محاسبه کند.

ورودی

در خط اول ورودی دو عدد طبیعی $n$ و $q$ به‌ترتیب می‌آیند. $$1 \leq n \leq 3 \times 10^5$$ $$0 \leq q \leq 3 \times 10^5$$ در خط دوم ورودی $n$ عدد می‌آید که به ترتیب مقادیر $p_i$ را مشخص می‌کنند.

در خط سوم ورودی $n$ عدد می‌آید که به ترتیب مقادیر اولیه $b_i$ را مشخص می‌کنند.

در $q$ خط بعدی در هر خط دو عدد $x_i$ و ‌ $y_i$ می آیند که تغییر $i$ ام را نشان می‌دهند و باید تغییر $b_{x_i} = y_i$ باید صورت بگیرد. $$1 \leq p_i , x_i \leq n$$ $$1 \leq b_i , y_i \leq 10^9$$

خروجی

در $q+1$ خط ، در خط اول کمترین میزان خستگی جمشید برای پاک کردن جایگشت قبل از اعمال تغییرات و به ترتیب در خط $i+1$ ام ، کمترین میزان خستگی جمشید برای پاک کردن جایگشت پس از اعمال $i$ تغییر اول را خروجی دهید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۵	$b_i=1$ و $q=0$
۲	۱۰	$q=0$ و $n=20$
۳	۲۵	$q=0$
۴	۲۵	$1 \le b_i \le 10$ و $1 \le y_i \le 10$
۵	۳۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

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

خروجی نمونه ۱

7
6

در این مثال قبل از تغییرات کافی است عدد $3$ و اعداد کوچکتر سمت چپ آن را پاک کنیم و به مقدار $4$ واحد خسته می‌شویم و سپس تنها عدد باقی‌مانده عدد $4$ است که آن را حذف می‌کنیم و به مقدار $3$ خسته می‌شویم که در کل $7$ واحد خسته می‌شویم.

پس از تغییر $b_2 = 3$ ابتدا عدد $2$ و اعداد کوچکتر چپ آن را حذف می‌کنیم و سپس عدد $4$ و اعداد کوچکتر سمت راست آن که در انتها کل جایگشت حذف می‌شود و میزان کل خستگی $6$ خواهد بود.

ورودی نمونه ۲

5 2
4 5 1 3 2
6 8 1 3 2
1 3
4 1

خروجی نمونه ۲

12
11
10