+ محدودیت زمان: ۱.۵ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران
----------
جمشید از جایگشت‌ها بدش می‌آید
و یک جایگشت
به طول
$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
```