ŠIOM — Traukiniai

Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Duomenų failas: traukiniai.in

Rezultatų failas: traukiniai.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Traukiniai

Mindaugas kiekvieną dieną keliauja traukiniu. Lietuvoje yra $n$ traukinių stočių ir $i$ -tojoje stotyje galima nusipirkti bilietus tik į stotis nuo $i+1$ iki $a_i$ įskaitant. Paskutinėje stotyje bilietai neparduodami.

Tarkime, jog $p_{i,j}$ yra minimalus reikalingų bilietų skaičius norint nuvykti iš stoties $i$ į stotį $j$ . Mindaugas nori suskaičiuoti visų porų $p_{i,j}$ $(1\\leqi\\leqj\\leqn)$ sumą. Padėkite jam tai padaryti.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius $n$ ( $2\\leqn\\leq100000$ ) - traukinių stočių skaičius.

Sekančioje eilutėje pateikta $n-1$ skaičių $a_i$ ( $i+1\\leqa_i\\leqn$ ), $i$ -tasis skaičius reiškia, jog stotyje $i$ galima nusipirkti bilietus iki stočių nuo $i+1$ iki $a_i$ .

Rezultatai

Išveskite vieną skaičių - $p_{i,j}$ sumą tarp visų porų $1\\leqi\\leqj\\leqn$ .

Pavyzdžiai

Pradiniai duomenys	Rezultatai
5 2 3 5 5	17

Šeštadieninė informatikos olimpiadininkų mokykla

Traukiniai

Pradiniai duomenys

Rezultatai

Pavyzdžiai