양의 정수 n과 양의 정수로 이루어진 수열 a₁, ... , a_n이 주어진다.

이때 a_i는 {{i\times(i-1)}\over 2} < a_i\leq {{i\times(i+1)}\over 2} 를 만족한다.

이 수열은 {(n+1)\times(n+2)}\over2개의 정점으로 이루어진 트리를 표현한다.

구체적으로 이 트리는 깊이 i인 정점이 i개씩 깊이 n+1까지 있는 형태이다.

이 트리가 갈라지는 형태는 깊이 i에서는 a_i가 자식이 둘이고 나머지는 모두 하나인 형태이다.

이때 정점들은 좌에서 우로 번호순으로 배열되어 그림과 같은 형태를 만든다.

당신은 "정점 x와 y의 LCA(가장 가까운 공통 조상)는 무엇인가?"라는 형태의 q개의 질문을 해결해야 한다.

가지치기 timer 4s memory 1024MB

가지치기 4s 1024MB