레몬 왕국의 용사, 비타로

용감한 용사 비타로는 던전 퀘스트에 도전한다.

던전은 $0,1,\dots,N-1$번까지 번호가 붙은 $N$개의 방으로 이루어져 있다. $0$번 방을 제외한 각 방은 정확히 하나의 상위 방을 가진다. $i$번 방($i \ge 1$)의 상위 방은 $P[i]$번 방이며, 반대로 $i$번 방은 $P[i]$번 방의 하위 방이다. 한 방은 여러 개의 하위 방을 가질 수 있으며, $0$번 방은 상위 방을 가지지 않는다.

비타로는 다음 규칙에 따라 방을 탐사한다.

처음에는 반드시 $0$번 방을 탐사한다.
이후에는 아직 탐사하지 않은 방 중에서, 그 상위 방이 이미 탐사된 방을 하나 골라 탐사한다.

던진의 $i$번 방은 난이도 $R[i]$와 레벨 $L[i]$를 가진다. 각 방의 레벨 $L[i]$는 변하지 않는다. 난이도 $R[i]$는 $i$번 방에서 출발하여 하위 방 방향으로 $0$번 이상 이동해 도달할 수 있는 방들 중, 이미 탐사한 방의 개수로 정의된다. 따라서 아직 탐사하지 않은 방의 난이도는 $0$이고, $0$번 방의 난이도는 항상 지금까지 탐사한 방의 개수이다.

새로운 방을 탐사할 때마다 던전에 있는 모든 방에 다음 규칙이 적용된다. 이에 따라 일부 방에 몬스터가 추가될 수 있다. 이미 탐사한 방에서 몬스터가 추가될 수 있음에 유의하라.

$L[i] \le R[i]$이면, $i$번 방에는 $L[i] + (L[i] + 1) + \cdots + R[i]$ 마리의 몬스터가 새로 추가된다.
$L[i] > R[i]$이면, $i$번 방에는 몬스터가 추가되지 않는다.
난이도가 $0$인 방(아직 탐사하지 않은 방)에는 몬스터가 추가되지 않는다.

비타로는 싸움을 최소화하고 싶기 때문에, 새로운 방을 탐사할 때는 탐사 직후 던전 전체에 새로 추가되는 몬스터 수가 최소가 되는 방을 선택한다. 만약 그런 방이 여러 개라면, 번호가 가장 작은 방을 선택한다.

하지만 비타로는 $P[i]$는 알지만 $L[i]$는 모른다. 이를 위해 그는 탐사할 수 있는 방 중 하나를 선택하여 조사하고, 그 방의 레벨 $L[i]$를 알 수 있다.

비타로가 던전 퀘스트를 성공적으로 마칠 수 있게 도와주자.

레몬 왕국의 용사, 비타로

문제

제한