Вася каждый день ездит на электричке. В Васином городе есть n остановок, причём на i-й остановке можно купить билет до любой остановки от (i + 1)-й до ai-й. На конечной остановке билеты не продаются.
Пусть ρi, j — минимальное количество билетов, которое нужно купить, чтобы добраться от i-й остановки до j-й. Вася любит собирать всякую бесполезную статистику, поэтому он просит вас найти сумму всех значений ρi, j по всем 1 ≤ i < j ≤ n.
Выходные данные
Выведите сумму ρi, j по всем 1 ≤ i < j ≤ n.
Примечание
В первом примере от каждой остановки до каждой можно добраться, купив один билет. Всего пар остановок 6, поэтому ответ тоже равен 6.
Во втором примере
- ρ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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 4 4
|
6
|
|
2
|
5
2 3 5 5
|
17
|