A. Баавгай ба өнгөнүүд

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

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

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

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

Лимак баавгайд нэг урт мөрөнд байрласан $n$ ширхэг будагдсан бөмбөгнүүд байв. Бөмбөгнүүд нь зүүнээс баруун хүртэл $1$-ээс $n$ хүртэл дугаарлагдсан байжээ. Түүнчлэн нийт $n$ ширхэг боломжит өнгө байгаа бөгөөд эдгээр өнгөнүүд нь мөн $1$-ээс $n$ хүртэл дугаарлагдсан байв. $i$-дахь бөмбөг нь $t_{i}$ өнгөтэй гэж үзье.

Эдгээр бөмбөгнүүдийн нэгэн тогтсон интервалын (дараалсан элементүүдийн олонлог) хувьд бид давамгайлж буй өнгийг тодорхойлох юм. Уг давамгайлж буй өнгө гэдэг нь уг интервал-д хамгийн олон тооны удаа давхцаж буй өнгийг хэлэх ажээ. Хэрэв хэсэг өнгөнүүд нь хамгийн олон удаа давхцах бөгөөд ижил тооны удаа уг интервалд давхацсан байвал эдгээр өнгөнүүдийн хамгийн бага дугаартай (индекстэй) өнгийг давамгайлж буй өнгө хэмээн үзэх юм.

Нийтдээ ширхэг интервалууд байх бөгөөд та өнгө болгоны хувьд уг өнгө давамгайлж буй интервалуудын тоог тооцох ёстой болжээ.

Оролт

Эхний мөрөнд бөмбөгнүүдийн тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 5000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ n$)-ууд өгөгдөх ба энд $t_{i}$ нь $i$-дахь бөмбөгний өнгийг илэрхийлэх юм.

Гаралт

$n$ ширхэг бүхэл тоо хэвлэх ба эдгээрийн $i$-дахь тоо нь $i$ гэсэн өнгө давамгайлж байх интервалуудын тоотой тэнцүү байх ёстой.

Орчуулсан: Баатархүү

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

Оролт
4
1 2 1 2
Гаралт
7 3 0 0 
Оролт
3
1 1 1
Гаралт
6 0 0 

Тэмдэглэл

Эхний жишээнд $2$ гэсэн өнгө нь 3 ширхэг интервалд давамгайлж байна:

  • $[2, 2]$ гэсэн интервал нь нэг ширхэг бөмбөг агуулна. Уг бөмбөгний өнгө нь $2$ учраас уг өнгө нь давамгайлж буй өнгө болох нь тодорхой юм.
  • $[4, 4]$ гэсэн интервал нь мөн л $2$ гэсэн өнгөтэй нэг ширхэг бөмбөг агуулж байх юм.
  • $[2, 4]$ гэсэн интервал нь $2$ гэсэн өнгөтэй 2 бөмбөг болон $1$ гэсэн өнгөтэй нэг бөмбөг агуулж байна.

Түүнчлэн эдгээрээс гадна $7$ ширхэг интервал байх бөгөөд эдгээр бүх интервалуудын хувьд $1$ гэсэн өнгө давамгайлж байна.

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