F. Овоолгуудын овоолго

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

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

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

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

Андрей бүтэн улирлын турш 'Алгоритмууд ба Өгөгдлийн Бүтцүүд' хичээлийн цагуудыг тасалчихсан. Тэр эцсийн шалгалтанд ирэх үед багш түүнд шийтгэл болгож хэцүү ажил өгөхөөр шийдсэн.

Багш Андрейд $n$ тоонуудын массив $a_{1}$, $...$, $a_{n}$ өгсөн. Үүний дараа тэр Андрейгаас 1-с $n - 1$ хүртэлх бүх $k$-н хувьд массив дээр $k$-д хамааралтай овоолгыг үүсгэх ба хамгийн бага оройтой овоолгын шинж чанартай зөрчилдөх элементүүдийн тоог олохыг даалгасан (өөрөөр элементийн утга нь эцэг зангилааны утгаас их байна).

Андрей Википедиа дээрээс $k$-д хамааралтай овоолго гэдэг нь массивын элементүүдтэй оройнуудтай үндэстэй мод гэдгийг харсан. Хэрвээ массивын элементүүд $1$-c $n$ хүртэл дугаарлагдсан бол $v$ элементийн хүүхдүүд нь $k(v - 1) + 2$, $...$, $kv + 1$ индекстэй элементүүд юм (хэрвээ эдгээр элементүүдийн зарим нь массивын хүрээнээс хальсан бол харгалзах хүүхдүүд нь байхгүй). Дурын $k$-д хамааралтай овоолгод эхний нэг элементээс бусад бүх элементүүд яг нэг эцэгтэй ба 1 дугаартай элементийн хувьд эцэг байхгүй (энэ элемент нь овоолгын үндэс). $v$ дугаартай элементийн эцгийн дугаарыг $p(v)$ гэж тэмдэглэ. Үндэс биш элементийн хувьд $a_{v} < a_{p(v)}$ байвал овоолгын шинж чанар зөрчилдөнө.

Андрейд уг ажлыг хийхэд туслана уу!

Оролт

Эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($2 ≤ n ≤ 2*10^{5}$) байна.

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

Гаралт

Нэг мөрөнд $n - 1$ бүхэл тоонуудыг хэвлэх ба дараалласан тоонуудыг зайгаар тусгаарла. $k = 1$, $2$, $...$, $n - 1$-н хувьд $k$-д хамааралтай овоолгын шинж чанартай зөрчилдсөн элементүүдийн дугаар.

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Эхний жишээний овоолгууд доорх зургуудаар өгөгдөв; овоолгын шинж чанартай зөрчилсөн элементүүд улаанаар тэмдэглэгдсэн.

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

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