레몬 왕국의 용사, 비타로

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

던전은 $0, 1, 2 \dots N-1$의 번호가 붙은 $N$개의 방으로 이루어져 있다. $0$번 방을 제외한 각 방은 $1$개씩의 상위 방을 가진다. $i (1 \leq i)$번 방의 상위 방은 $P[i] (0 \leq P_i \lt i)$이다. 또한, 반대로 $i$번 방은 $P[i]$번 방의 하위 방이다. 한 방은 여러 개의 하위 방을 가질 수 있다. $0$번 방은 상위 방을 가지지 않는다.

비타로는 현재 던전 입구에 있다. 비타로는 다음 조건을 만족하도록 방을 차례차례 탐사해 나갈 것이다.

• 처음에는 무조건 $0$번 방을 탐사한다.
• 그 다음부터는 아직 탐사하지 않은 방 중 상위 방이 탐사된 방을 하나 골라 탐사한다.

던전의 $i$번 방은 난이도 $R[i]$와 레벨 $L[i]$를 가진다. 각 방의 레벨은 던전을 탐사하는 동안 변하지 않지만, 난이도는 던전을 탐사함에 따라서 바뀔 수 있다. 어떤 방의 난이도는, 그 방에서 출발해서 하위 방으로 $0$번 이상 이동해 도달할 수 있는 모든 방 중 탐사한 방의 개수이다. 즉 아직 탐사하지 않은 방의 난이도는 $0$이고, $1$번 방의 난이도는 항상 지금까지 탐사한 방의 개수와 같다.

새로운 방을 탐사할 때마다 일부 방에는 몬스터가 추가된다. 이미 탐사한 방에도 몬스터가 추가될 수 있다. 탐사를 진행한 직후 $i$번 방의 난이도 $R[i]$와 레벨 $L[i]$에 대해, $L[i] \leq R[i]$ 라면 $i$번 방에는 $L[i] + (L[i]+1) + \dots + R[i]$ 마리의 몬스터가 새로 등장한다. $L[i] \gt R[i]$ 이면 $i$번 방에는 몬스터가 추가로 등장하지 않는다. 난이도가 $0$인 방(즉, 아직 탐사하지 않은 방)에는 몬스터가 등장하지 않음에 유의하라.

비타로는 최대한 싸움을 피하고 싶기 때문에, 새로운 방을 탐사할 때는 탐사할 수 있는 방 중 그 방을 탐사한 직후 던전 전체에 생성되는 몬스터의 수가 최소가 되는 방을 선택해 탐사할 것이다. 만약 그런 방이 여러 개라면, 그중 번호가 제일 작은 방을 방문하려 한다.

하지만 비타로는 던전의 지도만 갖고 있기 때문에, $P[i]$는 알지만 $L[i]$는 알지 못한다. 이를 위해, 비타로는 새로 탐사할 수 있는 방 하나를 골라 조사해 그 방의 레벨 $L[i]$를 얻을 수 있다.

비타로를 도와 비타로가 무사히 던전을 퀘스트를 끝낼 수 있게 해주자.

<div>함수 구현</div><div>함수 구현에 앞서 #include "brave.h" 를 통해 "brave.h" 헤더 파일을 포함해야 한다.</div><div><br></div><div>당신은 다음 함수를 구현해야 한다.</div><div><br></div><div>void bitaroTravel(int N, std::vector&lt;int&gt; P)</div><div> </div><div>$N$: 방의 수</div><div> </div><div>$P$: 각 방의 상위 방을 나타내는 길이&nbsp;</div><div>$N$의 배열&nbsp;</div><div>$(P[0] = 0$으로 정의된다</div><div>$)$ </div><div>이 함수는 하나의 테스트 케이스에 대해 단 한 번만 호출된다.</div><div>이 함수 안에서 아래의 두 함수를 호출해 비타로의 탐험을 시뮬레이션해야 한다.</div><div><br></div><div>int explore(int i)</div><div> </div><div>$i$: 새롭게 탐사할 방의 번호 (</div><div>$0 \le i \le N - 1$)</div><div>첫 번째 호출에서는 반드시&nbsp;</div><div>$0$번 방을 탐사해야 한다.</div><div>이후 호출에서는&nbsp;</div><div>$i$번 방이 아직 탐사되지 않았고,&nbsp;</div><div>$P[i]$번 방이 이미 탐사된 상태여야 한다.</div><div>조건에 맞지 않으면&nbsp;</div><div>$-1$을 반환한다. (탐사 규칙 위반 여부와는 별개이다.)</div><div>그 외의 경우&nbsp;</div><div>$1$을 반환한다.</div><div>int investigate(int i)</div><div> </div><div>$i$: 조사할 방 번호 (</div><div>$0 \le i \le N - 1$)</div><div>이때&nbsp;</div><div>$i$번 방은 탐사되지 않았고,&nbsp;</div><div>$P[i]$번 방은 탐사된 상태여야 한다.</div><div>모든 방은 단 한 번만 조사할 수 있다. 즉, 같은 방을 여러 번 조사할 수 없다.</div><div>조건을 만족하지 않으면&nbsp;</div><div>$-1$을 반환한다.</div><div>그 외의 경우&nbsp;</div><div>$L[i]$을 반환한다.</div><div>explore 함수를 총&nbsp;</div><div>$N$번 호출해 모든 방을 탐험한 뒤에는 bitaroTravel 함수를 종료해야 한다.</div><div><br></div><div>종료 후, 방을 탐사한 순서가 문제의 조건에 맞으면 맞았습니다!! 판정을, 그렇지 않으면 틀렸습니다 판정을 받는다.</div><div><br></div><div>제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.</div><div><br></div>

전체 문제에 대해 $2 \leq N \leq 3 \times 10^5$ $1 \leq L_i \leq 10$

서브태스크

부분문제 1. (11점) $N \leq 400$

부분문제 2. (13점) $N \leq 2000$

부분문제 3. (23점) 모든 i에 대해 $P_i = i/2$

부분문제 4. (32점) $N \leq 5 \times 10^4$

부분문제 5. (21점) 추가 제한 없음.