دلاکس (Delax)

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

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

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

در $q$ خط بعدی در هر خط دو عدد $x_i$ و ‌ $y_i$ می آیند که تغییر $i$ ام را نشان می‌دهند و باید تغییر $b_{x_i} = y_i$ باید صورت بگیرد.

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

• زیرمسئله اول (۵ نمره): $\forall 1 \leq i \leq n : b_i = 1$ و $q = 0$
• زیرمسئله دوم (۱۰ نمره): $n = 20$ و $q = 0$
• زیرمسئله سوم (۲۵ نمره): $q = 0$
• زیرمسئله چهارم (۲۵ نمره): $\forall 1 \leq i \leq n : 1 \leq y_i, b_i \leq 10$
• زیرمسئله پنجم (۳۵ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq n \leq 3 \times 10^5$
• $ 0 \leq q \leq 3 \times 10^5$
• $1 \leq p_i, x_i \leq n$
• $1 \leq b_i, y_i \leq 10^9$
• تضمین می‌شود $p$ یک جایگشت است.

• سوال قبل