D. Азтай хос

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

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

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

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

Пэтя азын тоонд их дуртай. Азын тоо гэдэг нь зөвхөн $4$ ба $7$ гэсэн цифрүүдээс бүрдсэн эерэг бүхэл тоонууд юм. Жишээ нь $47$, $744$, $4$ нар нь азын тоо ба $5$, $17$, $467$ нар нь биш юм.

Пэтяд $n$ гишүүнтэй $a$ гэсэн бүхэл тоон дараалал байгаа. Дарааллын гишүүд $1$-ээс эхлэн дугаарлагдсан. Харамсалтай нь Пэтя дүрсгүйтсэн тул эцэг эх нь түүнийг олон азын тоотой дарааллаар тоглохыг нь хоригложээ. $a$ дараалалд хамгийн ихдээ $1000$ азын тоо байх болно.

Пэтя $a[l_{1}..r_{1}]$ болон $a[l_{2}..r_{2}]$ дэд дарааллууд ижил азын тоо агуулаагүй байхаар $[l_{1};r_{1}]$ болон $[l_{2};r_{2}]$ ($1 ≤ l_{1} ≤ r_{1} < l_{2} ≤ r_{2} ≤ n$) гэсэн үл огтлолцох завсруудын тоог олох хэрэгтэй болжээ. Пэтяд энэхүү хосын тоог олоход туслаарай.

Оролт

Эхний мөрөнд $a$ дарааллын урт болох $n$ $(2 ≤ n ≤ 10^{5})$ байна. Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$) нар зайгаар тусгаарлагдан байна. Эдгээр дунд хамгийн ихдээ $1000$ ширхэг азын тоо байна.

Гаралт

Бодлогын хариуг хэвлэ.

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

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

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

Оролт
4
1 4 2 4
Гаралт
9
Оролт
2
4 7
Гаралт
1
Оролт
4
4 4 7 7
Гаралт
9

Тэмдэглэл

$a[l..r]$ дэд дараалал нь $a_{l}$, $a_{l+1}$, ..., $a_{r}$ гэсэн гишүүдтэй дараалал юм.

Эхний жишээнд нөхцөлийг хангах $9$ хос байгаа юм:

  • $[1, 1]$ ба $[2, 2]$
  • $[1, 1]$ ба $[2, 3]$
  • $[1, 1]$ ба $[2, 4]$
  • $[1, 1]$ ба $[3, 3]$
  • $[1, 1]$ ба $[3, 4]$
  • $[1, 1]$ ба $[4, 4]$
  • $[1, 2]$ ба $[3, 3]$
  • $[2, 2]$ ба $[3, 3]$
  • $[3, 3]$ ба $[4, 4]$

Хоёр дахь жишээнд цор ганц хос байгаа нь $[1;1]$ ба $[2;2]$ бөгөөд энэ нь нөхцөлийг хангах юм.

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