Есть \(n\) точек \(1,2,\ldots,n\), у каждой точки \(i\) написано число \(a_i\). Вы играете в игру на этих точках. Изначально вы находитесь в точке \(1\). Когда вы находитесь в точке \(i\), выполните следующий шаг:
- Если \(1\le i\le n\), перейдите к точке \(i+a_i\);
- В противном случае игра заканчивается.
Перед началом игры вы можете выбрать два целых числа \(x\) и \(y\), удовлетворяющих \(1\le x\le n\), \(-n \le y \le n\), и заменить число \(a_x\) на \(y\) (сделать \(a_x := y\)). Найдите количество различных пар \((x,y)\), при которых игра, которую вы начнете после замены, закончится за конечное число шагов.
Обратите внимание, что вам не нужно удовлетворять условию \(a_x\not=y\).
Выходные данные
Для каждого набора входных данных выведите строку, содержащую одно целое число — количество различных пар \((x,y)\), игра с которыми конечна.
Примечание
В первом наборе входных данных парами \((x,y)\), с которыми игра конечна, являются \((1,-1)\) и \((1,1)\), соответствующие маршрутам \(1\rightarrow 0\) и \(1\rightarrow 2\). Обратите внимание, что пара \((1,2)\) не подходит, так как при \(n=1\) равенство \(y=2\) нарушает \(-n\le y\le n\). \((1,0)\) также не подходит, так как вы всегда переходите от \(1\) к \(1\), и игра не заканчивается.
Во втором наборе входных данных подходящие пары равны \((1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)\).
В четвертом наборе входных данных подходящие пары \((1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)\).