====== دلاکس (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$ یک جایگشت است.

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 1 \\ 1 2 4 3 \\ 2 5 3 4 \\ 2 3 | 7 \\ 6 |
|5 2 \\ 4 5 1 3 2 \\ 6 8 1 3 2 \\ 1 3 \\ 4 1 | 12 \\ 11 \\ 10|
</WRAP>

  * [[سوال ۲|سوال قبل]]