+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
حنا وارد مسابقه *هندونه‌خوری* شده است. در این مسابقه $n$ هندوانه وجود دارد که به ترتیب با شماره‌های ۱ تا $n$ نام‌گذاری شده‌اند، هم‌چنین وزن هندوانه $i$ام، $w_i$ است. (وزن هندوانه‌ها متمایز است.)
حنا در هر مرحله از این مسابقه دو هندوانه‌ای که کمترین شماره را دارند را انتخاب می‌کند و هندوانه‌ای که سبک‌تر است را می‌خورد. حنا به این کار ادامه می‌دهد تا فقط یک هندوانه باقی بماند.
بعد از مسابقه حنا به این فکر رفته که آخرین هندوانه چه شماره‌ای داشت اما از آن‌جا که خیلی هندوانه خورده، فکرش کار نمی‌کند. به حنا کمک کنید و با گرفتن $w_i$ ها شماره آخرین هندوانه را بگویید.
# ورودی
در سطر اول $n$ تعداد هندوانه‌ها آمده است.
در سطر بعدی $w_1, w_2, \ldots, w_n\ $ آمده است.
$$ 1 \leq n \leq 100 $$
$$ 1 \leq w_i \leq 100 $$
+ تضمین می‌شود که $w_i$ ها متمایز هستند.
# خروجی
در تنها سطر خروجی شماره هندوانه باقی مانده را چاپ کنید.
# مثال
# ورودی نمونه ۱
```
5
4 3 1 5 2
```
# خروجی نمونه ۱
```
4
```
در این نمونه به ترتیب اتفاق‌های زیر اتفاق می‌افتد.
+ هندوانه‌های ۱ و ۲ انتخاب می‌شوند و هندوانه ۲ چون وزن کم‌تری دارد خورده می‌شود.
+ هندوانه‌های ۱ و ۳ انتخاب می‌شوند و هندوانه ۳ خورده می‌شود.
+ هندوانه‌های ۱ و ۴ انتخاب می‌شوند و هندوانه ۱ خورده می‌شود.
+ هندوانه‌های ۴ و ۵ انتخاب می‌شوند و هندوانه ۵ خورده می‌شود.
در نهایت هندوانه چهار باقی می‌ماند.
# ورودی نمونه ۲
```
5
2 4 5 1 3
```
# خروجی نمونه ۲
```
3
```
<details class="blue">
<summary>
راهنمایی ۱
</summary>
ثابت کنید که هندوانه‌ای که در انتها باقی می‌ماند بیشترین وزن را میان هندوانه‌ها دارد.
</details>
<details class="blue">
<summary>
راهنمایی ۲
</summary>
با استفاده از یک حلقه، ابتدا مقدار بیشنیه وزن را در آرایه $w$ محاسبه کنید. سپس با استفاده از یک حلقه دیگر اندیسی که مقدار بیشینه را دارد پیدا و آن را چاپ کنید.
</details>
هندونه‌خوری
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
حنا قهرمان مسابقات *هندونه‌خوری* شده و مقدار زیادی پول جایزه گرفته است. حال حنا می‌خواهد به خانه‌اش برگردد و با پول مسابقات مهمانی بگیرد.
شهر محل زندگی حنا، یک خیابان با $n$ خانه است که حنا در خانه‌ی $s$ام زندگی می‌کند و مسابقات *هندونه‌خوری* در خانه $t$ ام برگزار می‌شود. او می‌داند در تعدادی از خانه‌ها زورگیر زندگی می‌کند و اگر از آن‌ها رد شود، زورگیر پول حنا را از او می‌گیرند و حنا نمی‌تواند مهمانی بگیرد.
حنا از پلیس کمک می‌خواهد. پلیس‌ها در روز برنامه‌نویس می‌توانند در هر عملیات، یک بازه به طول $2^k$ ($k$ یک عدد حسابی است) را که **همه اعضای** آن زورگیر هستند را انتخاب کنند و آن خانه‌ها را پاکسازی کنند.
پلیس‌ها وقت زیادی ندارند. برای همین از شما می‌خواهند کمترین تعداد عملیات برای پاکسازی مسیر بین حنا و مسابقه *هندونه‌خوری* را بگویید.
# ورودی
در سطر اول عدد $n$ آمده که نشان‌دهنده‌ی طول خیابان است.
در سطر دوم یک رشته به طول $n$ آمدهاست. خانه‌هایی که در آن زورگیر وجود دارد حرف `H` و بقیه خانه‌ها حرف `P` هستند. تضمین می‌شود که در خانه‌های $s$ و $t$ زورگیر وجود ندارد.
در سطر سوم $s$ و $t$ به ترتیب آمده‌اند.
$$ 1 \leq n \leq 1\ 000 $$
$$ 1 \leq s, t \leq n $$
# خروجی
در تنها سطر خروجی، کمترین تعداد عملیات برای پاکسازی مسیر حنا از زورگیرها را بگویید.
# مثال
# ورودی نمونه ۱
```
3
PHP
1 3
```
# خروجی نمونه ۱
```
1
```
در مسیر خانه اول به سوم، تنها در خانه دوم زورگیر وجود دارد که پلیس‌ها طی یک مرحله او را دستگیر می‌کنند.
# ورودی نمونه ۲
```
9
HPPHHPHPH
8 3
```
# خروجی نمونه ۲
```
2
```
در مسیر خانه هشتم به سوم تنها در خانه‌های ۴ و ۵ و ۷ زورگیر وجود دارد که پلیس‌ها طی یک مرحله زورگیر خانه‌ی ۴ و ۵ و در مرحله‌ی بعد زورگیر خانه‌ی ۷ را دستگیر می‌کنند. در حرکت اول یک بازه به طول ۲ و در حرکت دوم یک بازه به طول ۱ پاکسازی شد که طول هر دو بازه توانی از ۲ بود.
<details class="blue">
<summary>
راهنمایی ۱
</summary>
باید زیربازه‌ی خانه $s$ام تا خانه $t$ام را در نظر بگیریم، چرا که بقیه‌ی خانه‌ها تاثیری در مسیر حنا به مسابقه ندارند. حال در این مسیر نیز می‌توانیم بلوک‌های متشکل از خانه‌های سالم را در نظر نگرفته و فقط بلوک‌های خانه‌های حاوی زورگیر را نگاه کنیم (منظور از بلوک تعدادی خانه‌ی متوالی است که ویژگی ما را ندارند و خانه‌های دو سر بلوک ویژگی ما را ندارند).
</details>
<details class="blue">
<summary>
راهنمایی ۲
</summary>
حال که خانه‌ها را بلوک‌بندی کردیم و فقط بلوک‌های دارای زورگیر را در نظر می‌گیریم، مسئله را به صورت مجزا برای بلوک‌ها حل می‌کنیم.
حال بلوک زورگیر خاصی را در نظر می‌گیریم. بدون لطمه خوردن به کلیت مسئله فرض می‌کنیم که اندازه‌ی بلوک مورد نظر برابر $m$ باشد. با کمی بررسی (در مبنای ۲) متوجه می‌شویم که بهینه‌ترین کار ممکن این است که هر دفعه پلیس‌ها بلندترین پیشوندی که می‌توانند را از بلوک فعلی پاکسازی نمایند. به عبارت دیگر، در هر مرحله $2^{k}$ خانه اول را از زورگیر پاکسازی می‌کند به طوری که
$$2^{k} \le m \le 2^{k+1}$$
و سپس مقدار $m$ را برابر اندازه‌ی بلوک جدید قرار می‌دهد (مقدار آن را منهای دو به توان $k$ می‌کند).
در واقع اگر در مبنای ۲ به $m$ نگاه کنیم، **حداقل تعداد گامی که لازم است تا این بازه را پاکسازی کنیم، برابر تعداد بیت‌های یک $m$ در مبنای ۲ می‌باشد.**
</details>
پاکسازی
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
دوستان حنا برای هدیه تولد او $n$ شیرینی خریده‌اند و آن‌ها را پشت سر هم روی میز قرار داده‌اند. آن‌ها به حنا گفته‌اند که وزن شیرینی $i$ ام $w_i$ است (ممکن است وزن یک شیرینی منفی باشد!). حالا حنا می‌خواهد یک بازه پشت سر هم از شیرینی‌ها را انتخاب کند و بخورد. اما از آنجایی که حنا رژیم دارد، مجموع وزن شیرینی‌هایی که می‌خورد، نمی‌تواند بیشتر از $W$ باشد. حنا که گیج شدهاست به شما روی آورده تا به او بیشترین وزن شیرینی که می‌تواند بخورد را بگویید.
توجه کنید که حنا همیشه گزینه شیرینی نخوردن را دارد و جواب حداقل صفر هست.
# ورودی
در سطر اول عدد $n$ و $W$ به ترتیب آمدهاست.
در سطر بعدی $\, w_1, w_2, \ldots, w_n $ به ترتیب آمدهاست.
$$1 \leq n \leq 300 \, 000$$
$$ -10^9 \leq w_i\leq 10^9 $$
$$ 1 \leq W \leq 10^9$$
# خروجی
بیشینه وزن شیرینی که حنا در مجموع می‌تواند بخورد را خروجی دهید.
# مثال
## ورودی نمونه ۱
```
3 7
4 5 3
```
## خروجی نمونه ۱
```
5
```
حنا تنها می‌تواند بازه $[2,2]$ را انتخاب کند.
## ورودی نمونه ۲
```
5 10
1 1 8 3 1
```
## خروجی نمونه ۲
```
10
```
در اینجا می‌توانیم بازه $[1,3]$ را انتخاب کنیم.
## ورودی نمونه ۳
```
5 10
13 -1 7 -12 19
```
## خروجی نمونه ۳
```
7
```
در اینجا می‌توانیم بازه $[1,4]$ را انتخاب کنیم.
<details class="blue">
<summary>
راهنمایی ۱
</summary>
هر بازه را می‌توانید به چشم حاصل تفریق دو پیشوند نگاه کنید. به عبارت دیگر، اگر $sum_i$ را حاصل جمع وزن $i$ شیرینی اول در نظر بگیرید، وزن هر بازه‌ای از شیرینی‌ها را می‌توان به صورت حاصل تفریق دو تا از این متغیرها دید:
$$sum_i,_j = sum_j - sum_i$$
سعی کنید با توجه به آرایه $sum$ سوال را حل کنید.
</details>
<details class="blue">
<summary>
راهنمایی ۲
</summary>
فرض کنید پایان بازه را فیکس کرده‌ایم (برای مثال عنصر $j$). حال اگر فرض کنیم متغیر $i$ نشان‌دهنده‌ی شروع بازه باشد. می‌توانیم کرانی برای $sum_j$ به دست آوریم. رابطه‌ای که در قسمت قبل گفتیم را می‌توان به این شکل بازنویسی کرد:
$$sum_i = sum_j - sum_i,_j$$
از آنجایی که می‌دانیم حداکثری وزنی که حنا می‌تواند بخورد $W$ است، رابطه‌ی زیر برقرار است:
$$sum_i <= sum_j - W$$
</details>
زیربازه
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
پدر حنا برای هدیه تولد او، صندوقچه‌ی پدربزرگش را باز کرده‌است و تکه کد زیر را به او داده‌است. (کد زیر یک شبه‌کد است و می‌توانید درباره شبه‌کد در [اینجا](https://fa.wikipedia.org/wiki/%D8%B4%D8%A8%D9%87%E2%80%8C%DA%A9%D8%AF) بخوانید.)
```
procedure old_little_code()
p := the input array of size n
s := an empty stack
a := an array of size 2n
counter = 1
for i = 1 to n inclusive do:
while s is not empty and p[s.top] < p[i] do:
a[counter] = s.top
counter += 1
s.pop()
end while
s.push(i)
a[counter] = s.top
counter += 1
end for
while s is not empty do:
a[counter] = s.top
counter += 1
s.pop()
end while
return a
end procedure
```
در کنار این تکه کد، کاغذی پیدا کرده و آن را نیز به حنا می‌دهد. روی کاغذ نوشته شده "به این تکه کد یک جایگشت از اعداد $1$ تا $n$ را دادم و در خروجی اعداد $a_1, a_2, \ldots, a_{2n}\ $ را گرفتم.". حنا قصد دارد جایگشتی که پدربزرگش به عنوان ورودی به تکه کد داده بود را پیدا کند. به او کمک کنید تا تعداد جایگشت‌های مختلفی که می‌توانند جایگشت پدربزرگش باشند را پیدا کند.
# ورودی
در سطر اول عدد $n$ آمدهاست.
در سطر بعدی، اعداد $a_1, a_2, \ldots, a_{2n}$ به ترتیب آمده‌اند.
تضمین می‌شود که به ازای حداقل یک جایگشت، خروجی داده‌شده تولید می‌شود.
$$ 1 \leq n \leq 200 \, 000 $$
$$ 1 \leq a_i \leq n $$
# خروجی
در تنها سطر خروجی، باقی‌مانده‌ی تعداد جایگشت‌ها بر $10^9 + 7$ را چاپ کنید.
# مثال
# ورودی نمونه ۱
```
2
1 2 2 1
```
# خروجی نمونه ۱
```
1
```
جایگشت پدربزرگ فقط می‌تواند $\{2, 1\}$ باشد.
# ورودی نمونه ۲
```
3
1 2 3 3 2 1
```
# خروجی نمونه ۲
```
1
```
جایگشت پدربزرگ فقط می‌تواند $\{3, 2, 1\}$ باشد.
# ورودی نمونه ۳
```
4
1 2 2 3 3 1 4 4
```
# خروجی نمونه ۳
```
1
```
جایگشت پدربزرگ فقط می‌تواند $\{3, 1, 2, 4\}$ باشد.
# ورودی نمونه ۴
```
5
1 2 2 3 3 4 5 5 4 1
```
# خروجی نمونه ۴
```
3
```
<details class="blue">
<summary>
راهنمایی ۱
</summary>
سعی کنید ثابت کنید که از روی خروجی شبه‌کد می‌توان جایگاه عدد $n$ را به طور یکتا پیدا کرد، سپس آن جایگاه را پیدا کنید.
</details>
جایگشت پدربزرگ
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
همان طور که می‌دانید حنا به ریاضیات علاقه خاصی دارد. او برای این که این علاقه را به دوستانش ثابت کند، آن‌ها را به چالش زیر دعوت می‌کند.
هر کدام آن‌ها باید دو عدد $n$ و $k$ را انتخاب کنند و سپس حنا تمام دنباله‌های شامل اعداد طبیعی $a_1, a_2, ..., a_m\ $ را که ویژگی‌های زیر را دارند یادداشت می‌کند.
+ $1 \le m \le n$
+ $1 \le a_i \le k$
+ $\sum_{i=1}^{m} a_i = n$
برای مثال اگر $n = 3$ و $k = 2$ باشد، حنا دنباله‌های زیر را یادداشت می‌کند.
+ $(2, 1)$
+ $(1, 2)$
+ $(1, 1, 1)$
دوستان حنا که از مهارت حنا شگفت زده می‌شوند از او می‌خواهند تا به ازای هر دنباله حاصل‌ضرب اعضایش را محاسبه کند و در نهایت بگوید که چند مقدار متفاوت در این بین وجود دارد (در نمونه بالا این مقدار برابر با ۲ است)؛ اما چون حنا در ضرب کردن کمی مشکل دارد از شما می‌خواهد تا به او کمک کنید و جواب دوستانش را بدهید.
# ورودی
در سطر اول $n$ و $k$ به ترتیب آمدهاست.
$$1 \leq k \leq n \leq 30 \, 000 $$
# خروجی
در تنها سطر خروجی باقیمانده جواب مسئله را بر $10^9 + 7$ چاپ کنید.
# مثال
# ورودی نمونه ۱
```
4 2
```
# خروجی نمونه ۱
```
3
```
مقادیر مختلف حاصل‌ضرب در این مثال ۱ و ۲ و ۴ هستند.
# ورودی نمونه ۲
```
5 3
```
# خروجی نمونه ۲
```
5
```
<details class="blue">
<summary>
راهنمایی ۱
</summary>
ثابت کنید کافیست تا آرایه‌هایی را در نظر بگیریم که در آن $a_i$ اول باشد یا برابر با یک باشد.
</details>
افراز
+ محدودیت زمان: ۳ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
معلم حنا هدیه تولد به او یک درخت ریشه‌دار $n$ راسی داده که ریشه آن راس شماره $1$ است. روی راس شماره $i$ آن عدد $a_i$ نوشته شدهاست. حنا بعد از یادگرفتن الگوریتم [جستجوی عمق اول](https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A7%D9%88%D9%84_%D8%B9%D9%85%D9%82) تکه کد زیر را نوشته است.
```
b := an array of length n
time := 1
procedure DFS(T, a, v):
b[time] = a[v]
time += 1
label v as visited
for u in T.neighbors(v) do:
if not visited[u] do:
DFS(T, a, u)
end if
end for
end procedure
procedure countInversions()
DFS(T, a, 1)
return number of inversions in the array b
/* Number of inversions in the array b is the number of distinct pairs (i, j) such that 1 <= i < j <= n and b[i] > b[j] */
end procedure
```
حنا می‌خواهد تابع `countInversions` را فراخوانی کند. او می‌داند که خروجی این تابع به ترتیب همسایه‌های هر راس در تابع `DFS` وابسته است. به او کمک کنید، کمینه خروجی ممکن این تابع را پیدا کند.
در واقع حنا می‌خواهد طوری ترتیب همسایه‌های رئوس را انتخاب کند که تعداد نابه‌جایی‌های آرایه `b` کمینه بشود.
منظور از نابه‌جایی تعداد جفت‌های $1 \le i < j \le n$ است که $a_i > a_j$ باشد.
# ورودی
در سطر اول ورودی عدد $n$ آمدهاست.
در سطر دوم، اعداد $a_1, a_2, ..., a_n$ به ترتیب آمده‌اند.
در سطر سوم، اعداد $p_2, p_3, ..., p_n$، به ترتیب آمده‌اند که $p_i$ پدر راس شماره $i$ درخت معلم است.
$$ 1 \leq n \leq 1 \, 000 \, 000 $$
$$ 0 \leq a_i \leq 2 $$
$$ 1 \leq p_i < i $$
# خروجی
در سطر اول خروجی، کمینه خروجی تابع `countInversions` را چاپ کنید.
# مثال
# ورودی نمونه ۱
```
6
0 0 2 0 0 2
1 2 3 2 2
```
# خروجی نمونه ۱
```
1
```
# ورودی نمونه ۲
```
8
0 1 1 2 1 0 1 2
1 2 2 1 1 2 3
```
# خروجی نمونه ۲
```
0
```
# ورودی نمونه ۳
```
10
2 0 1 1 1 2 1 0 0 0
1 2 2 1 5 5 5 5 5
```
# خروجی نمونه ۳
```
16
```
<details class="blue">
<summary>
راهنمایی ۱
</summary>
ابتدا سعی کنید تابعی برای مقایسه‌ی بین دو تا از بچه‌های هر راس پیدا کنید که بگوید بهتر است اول وارد کدام بچه شود، سپس ثابت کنید این تابع، تابعی مناسب برای مرتب‌سازی بچه‌های یک راس از درخت است.
</details>
نابه‌جایی
+ محدودیت زمان: ۳ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
بعد از یک کلاس ریاضیات سخت، حنا برای تفریح به همراه بنا به جنگل رفته است. حنا و بنا هر کدام یک درخت (گراف بدون دور و همبند) ریشه‌دار $n$ راسی انتخاب کرده‌اند. آن‌ها به یک دنباله از اعداد مانند $V_1, V_2, ..., V_K$ *علاقه* دارند اگر هر دو شرط زیر برقرار باشد:
+ در درخت حنا، به ازای هر $1 \leq i < K$ راس $V_i$ جد راس $V_{i+1}$ است.
+ در درخت بنا، به ازای هر $1 \leq i < K$ راس $V_{i+1}$ جد راس $V_i$ است.
آن‌ها *عاشق* یک دنباله هستند اگر هر دو شرط زیر برقرار باشد:
+ به این دنباله علاقه داشته باشند.
+ هیچ دنباله‌ای با طول بیشتر از این دنباله وجود نداشته باشد که به آن علاقه داشته باشند.
در یک درخت ریشه‌دار، به راس $v$ *جد* راس $u$ می‌گوییم اگر یکی از دو شرط زیر برقرار باشد:
+ راس $v$ پدر راس $u$ باشد.
+ راس $v$ جد پدر راس $u$ باشد.
طول بزرگ‌ترین دنباله‌ای که حنا و بنا به آن علاقه دارند، و تعداد دنباله‌هایی که آن‌ها عاشق آن هستند، چقدر است؟
# ورودی
در سطر اول ورودی، عدد $n$ آمدهاست.
در $n - 1$ سطر بعدی یال‌های درخت حنا آمدهاست. در $i$ امین سطر $v_i$ و $u_i$ دو سر یال $i$ ام در درخت حنا آمدهاست. **ریشه درخت حنا راس شماره $1$ است.**
در $n - 1$ سطر بعدی یال‌های درخت بنا آمدهاست. در $i$ امین سطر $v_i$ و $u_i$ دو سر یال $i$ ام در درخت بنا آمدهاست. **ریشه درخت بنا راس شماره $n$ است.**
$$ 1 \leq n \leq 200 \, 000 $$
$$ 1 \leq v_i, u_i \leq n $$
# خروجی
در تنها سطر خروجی، طول بزرگ‌ترین دنباله‌ای که حنا و بنا به آن علاقه دارند و باقیمانده تعداد دنباله‌هایی که آن‌ها عاشق آن هستند را بر $10^9 + 7$ چاپ کنید.
# مثال
# ورودی نمونه
```
5
4 2
3 1
5 4
2 1
4 5
1 5
3 4
2 5
```
# خروجی نمونه
```
2 3
```
<details class="blue">
<summary>
راهنمایی ۱
</summary>
یک $dp$ تعریف کنید که در آن $dp_v$ برابر طول بلندترین دنباله است که پایین‌ترین راس ان در درخت اول، $v$ است و این$dp$ را به دست آورید.
</details>