E. Электрички и статистика
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася каждый день ездит на электричке. В Васином городе есть n остановок, причём на i-й остановке можно купить билет до любой остановки от (i + 1)-й до ai-й. На конечной остановке билеты не продаются.

Пусть ρi, j — минимальное количество билетов, которое нужно купить, чтобы добраться от i-й остановки до j-й. Вася любит собирать всякую бесполезную статистику, поэтому он просит вас найти сумму всех значений ρi, j по всем 1 ≤ i < j ≤ n.

Входные данные

В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 100 000) — количество остановок.

Во второй строке записано n - 1 целое число ai (i + 1 ≤ ai ≤ n) — означающее, что на остановке i можно купить билет на электричку до любой остановки от i + 1 до ai включительно.

Выходные данные

Выведите сумму ρi, j по всем 1 ≤ i < j ≤ n.

Примеры
Входные данные
4
4 4 4
Выходные данные
6
Входные данные
5
2 3 5 5
Выходные данные
17
Примечание

В первом примере от каждой остановки до каждой можно добраться, купив один билет. Всего пар остановок 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.