====== Permutation ======
به شما جایگشت ‎$p$‎ از اعداد ‎$1$‎ تا ‎$n$‎ داده شده است، شما باید تعداد ‎$1 \leq i \leq j \leq n$‎ هایی را بیابید که اعداد ‎$p_i$‎ تا ‎$p_j$‎ یک بازه پشت‌سرهم از اعداد را تشکیل می‌دهد.
برای مثال پاسخ سوال برای جایگشت ‎$<1,3,2,4>$ ‎ جفت $i$ و ‎$j$‎های زیر است:

  * ‎ $(1,1)$‎
  * ‎ $(2,2)$‎
  * ‎ $(3,3)$‎
  * ‎ $(4,4)$‎
  * ‎ $(1,3)$‎
  * ‎ $(1,4)$‎
  * ‎ $(2,4)$‎
  * ‎ $(2,3)$‎


===== ورودی =====
  * در سطر اول ورودی، عدد ‎$1 \leq n \leq 5000$‎ آمده است.‎
  *  در سطر بعدی، اعداد ‎$p_1$‎ تا ‎$p_n$‎ آمده‌اند.


===== خروجی =====
در تنها سطر خروجی تعداد ‎$(i,j)$‎های مورد نظر را چاپ نمایید.‎
===== محدودیت‌ها =====


  * محدودیت زمان: ۲ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

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

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4‎ \\ 1 3 2 4 | 8 |
|5‎ \\ 1 2 3 4 5 | 15 |

</WRAP>

<پاسخ>

فرض کنید بازه ‎$(i,j)$‎ یکی از بازه‌های مورد نظر ما باشد. چون تمام اعداد ‎$p_i$‎ ، ‎$p_{i+1}$‎ ، ‎$\cdots$‎ ، ‎$p_j$‎ در یک بازه قرار دارند، پس شرط زیر بر قرار است:

  * ‎ $max(p_i,p_{i+1},\cdots,p_j)‎ - ‎min(p_i,p_{i+1},\cdots,p_j) = j-i$‎

می‌توان نشان داد که اگر یک بازه  ‎$(i,j)$‎  شرط بالا را داشته باشد، اعداد ‎$p_i$‎ تا ‎$p_j$‎ در یک بازه قرار خواهند داشت‎.

‎
پس کافیست تعداد ‎$(i,j)$‎ هایی را بشماریم که شرط بالا را دارند‎.

‎
 برای این کار می‌توان ‎min[i][j] و ‎max[i][j] را برای همه اعداد ‎$1$‎ تا ‎$n$‎ به صورت پویا به‌دست بیاوریم و شرط گفته شده را برای تمام بازه‌ها چک کنیم‎.

 
‎
**پیچیدگی**

‎
ساختن آریه min و max‎ را می‌توان در زمان ‎$o(n^2)$‎ انجام داد و چک کردن هر بازه در زمان ‎$o(1)$‎ انجام می‌شود. پس می‌توان همه بازه‌ها را در زمان ‎$o(n^2)$‎ چک کرد. 

پیچیدگی زمانی الگوریتم گفته شده برابر با ‎$o(n^2)$‎ است.


</پاسخ>


  * [[سوال ۴۹|سوال بعد]]
  * [[سوال ۴۷|سوال قبل]]