D. Хоёр хэрчим

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Никд $1$-ээс $n$ хүртэлх тоонуудын $p$ гэсэн сэлгэмэл өгөгджээ. $[l, r]$ ($l ≤ r$) хэрчмээр $p_{i}$ ($l ≤ i ≤ r$) тоонуудыг илэрхийлье.

Хэрэв $[a_{0}, a_{1}]$ ба $[b_{0}, b_{1}]$ ($1 ≤ a_{0} ≤ a_{1} < b_{0} ≤ b_{1} ≤ n$)-ийн гишүүдийг нийлүүлэн өсөх эрэмбээр эрэмбэлсний дараа үүсэх $(a_{1} - a_{0} + b_{1} - b_{0} + 2)$ ширхэг гишүүнтэй дараалал $1$ гэсэн ялгавартай арифметик прогресс үүсгэдэг бол $[a_{0}, a_{1}]$ ба $[b_{0}, b_{1}]$ ($1 ≤ a_{0} ≤ a_{1} < b_{0} ≤ b_{1} ≤ n$) хэрчмүүдийн хосыг сайн гэе. Өөрөөр хэлбэл нийт гишүүдийг өсөхөөр эрэмбэлсний дараа ямар нэгэн $x$ болон $m$ тоонуудын хувьд ${x, x + 1, x + 2, ..., x + m - 1}$ хэлбэрийн дараалал гардаг байвал сайн гэх юм.

Чиний даалгавар бол өгөгдсөн $p$ тооны сэлгэмэлээс сайн хэрчмүүдийн хосын тоог олох юм. Хоёр хэрчмүүдийн хосыг хос бүрийн хэрчим дэх гишүүдээс тогтох олонлогууд ялгаатай үед тухайн хоёр хосыг ялгаатай гэж үзнэ. Тухайлбал $[l, i]$ болон $[i + 1, r]$ ($l ≤ i ≤ r$) хосын бүх гишүүд $[l, r]$ $(l < r)$ хэрчим үүсгэнэ. Нийт гишүүдээс нь үүссэн олонлог нь адилхан байх хосууд ижилхэн гэж тооцогдох юм.

Тайлбартай жишээг ажиглана уу.

Оролт

Эхний мөрөнд сэлгэмлийн хэмжээ болох $n$ ($1 ≤ n ≤ 3*10^{5}$) байна. Хоёр дахь мөрөнд $p_{i}$, ($1 ≤ p_{i} ≤ n$) тоонууд зайгаар тусгаарлагдан байна.

Гаралт

$p$ сэлгэмлийн сайн хэрчмүүдийн тоог ол.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
3
1 2 3
Гаралт
3
Оролт
5
1 4 5 3 2
Гаралт
10
Оролт
5
5 4 3 1 2
Гаралт
10

Тэмдэглэл

Эхний жишээнд дараах хосууд сайн: ($[1, 1]$, $[2, 2]$); ($[2, 2]$, $[3, 3]$); ($[1, 2]$, $[3, 3]$). Харин ($[1, 1]$, $[2, 3]$) ба ($[1, 2]$, $[3, 3]$) хосууд нь ижилхэн ${1, 2, 3}$ олонлогийг үүсгэх тул ижил хос гэж тооцогдож байгаа юм.

Дөрөв дэх жишээнд дараах хосууд нь сайн: ($[4, 4]$, $[5, 5]$); ($[3, 3]$,$[4, 5]$); ($[2, 2]$,$[3, 5]$); ($[1, 1]$,$[2, 5]$); ($[3, 3]$,$[5, 5]$); ($[2, 3]$,$[5, 5]$); ($[1, 3]$,$[5, 5]$); ($[2, 2]$,$[3, 3]$); ($[1, 1]$,$[2, 3]$); ($[1, 1]$,$[2, 2]$).

Сэтгэгдлүүдийг ачааллаж байна...