E. Галт тэрэгнүүд ба тоон үзүүлэлтүүд

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

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

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

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

Вася өдөр болгон галт тэргээр ажилдаа ирж очдог. Уг хотод нийт $n$ ширхэг галт тэрэгний зогсоол байдаг ба $i$-дахь зогсоолоос зөвхөн $i + 1$-ээс $a_{i}$-ын хооронд байх (эдгээр нь өөрсдөө мөн орно) зогсоол хүрэх тасалбар худалдан авах боломжтой. Түүнчлэн сүүлийн зогсоол дээр ямар ч тасалбар зардаггүй.

$i$-р зогсоолоос $j$-р зогсоол хүрэхийн тулд худалдан авах тасалбарын хамгийн бага тоог $ρ_{i, j}$-аар тэмдэглэе. Вася өөр нэгэн хэрэгцээгүй тоон үзүүлэлтэд дуртай учраас тэрээр танаас $1 ≤ i < j ≤ n$-ын хооронд байх бүх хосуудын $ρ_{i, j}$ утгуудын нийлбэрийг тооцоолж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд зогсоолын тоо болох бүхэл тоо $n$ ($2 ≤ n ≤ 100 000$) өгөгдөнө.

2-дахь мөрөнд $n - 1$ ширхэг бүхэл тоо $a_{i}$ ($i + 1 ≤ a_{i} ≤ n$)-ууд өгөгдөх ба эдгээрийн $i$-дахь нь та $i$-р зогсоолоос $i + 1$-ээс $a_{i}$-ын хооронд байх (эдгээр нь өөрсдөө мөн орно) зогсоол хүрэх тасалбар худалдан авах боломжтой гэдгийг илэрхийлнэ.

Гаралт

$1 ≤ i < j ≤ n$-ын хооронд байх бүх хосуудын $ρ_{i, j}$ утгуудын нийлбэрийг хэвлэнэ үү.

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

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

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

Тэмдэглэл

Эхний жишээнд аль ч зогсоолоос бусад аль ч зогсоол уруу (их дугаартай) зөвхөн 1 тасалбар ашиглан хүрэх боломжтой. Нийт хосын тоо нь $6$ байна иймд уг бодлогын хариу нь мөн $6$ байх юм.

2-дахь жишээг авч үзье:

  • $ρ_{1, 2} = 1$
  • $ρ_{1, 3} = 2$
  • $ρ_{1, 4} = 3$
  • $ρ_{1, 5} = 3$
  • $ρ_{2, 3} = 1$
  • $ρ_{2, 4} = 2$
  • $ρ_{2, 5} = 2$
  • $ρ_{3, 4} = 1$
  • $ρ_{3, 5} = 1$
  • $ρ_{4, 5} = 1$

Иймд бодлогын хариу нь $1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17$ байна.

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