A114507.小午的家族谱

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小午在整理家族谱。家族中有 nn 个人,编号为 11nn。其中,午枫是编号 11,小午是编号 nn

对于每个人 ii2in2 \le i \le n),我们知道他的父亲是 pip_i,并且满足 pi<ip_i < i(即父亲的编号一定小于自己的编号)。这意味着编号 11 是家族的祖先(他没有父亲)。

小午想知道,他和午枫之间隔了多少代?即从小午开始,向上追溯到午枫,需要经过几代人。

请你帮助小午计算这个代际距离。

输入格式

第一行一个整数 nn,表示家族中的人数。

第二行包含 n1n-1 个整数 p2,p3,,pnp_2, p_3, \dots, p_n,表示第 ii 个人的父亲是 pip_i

输出格式

输出一个整数,表示午枫(编号 11)和小午(编号 nn)之间隔的代数。

输入输出样例

  • 输入#1

    3
    1 2

    输出#1

    2
  • 输入#2

    10
    1 2 3 4 5 6 7 8 9

    输出#2

    9

说明/提示

样例 #1 解释

家族关系:第 22 个人的父亲是 11(午枫),第 33 个人的父亲是 22。所以午枫是第 22 个人的父亲,第 33 个人的祖父。因此,午枫(编号 11)和小午(编号 33)之间隔了 22 代(午枫 → 第 22 个人 → 小午)。

数据范围

对于 100%100\% 的测试数据,满足:2n50,1pii12 \le n \le 50, 1 \le p_i \le i-1,保证 pi<ip_i < i

首页