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

---

جمشید از جایگشت‌ها بدش می‌آید و یک جایگشت به طول \(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