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)$های مورد نظر را چاپ نمایید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4
1 3 2 4 		8
5
1 2 3 4 5 		15

پاسخ

فرض کنید بازه $(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)$ است.

▸ سوال قبل سوال بعد ◂