여러분은 0과 1로만 이루어진 길이 N의 수열을 받았다.

초기에 각 원소는 길이 1의 문자열을 의미한다.

이 수열에서 원소들을 합치는 연산을 N-1번 실행하려 한다.

원소를 합치는 것은 두 개의 문자열 S와 T가 있으면,

S와 T를 수열에서 지우고 "ST"를 새롭게 삽입하는 것으로 생각할 수 있다.

i번째 합치는 연산은 두 숫자 A_i, B_i로 표기할 수 있는데, 이는 초기 수열의 A_i번째 문자열이 속해 있는 문자열과

초기 수열의 B_i번째 문자열이 속해 있는 문자열을 합치는 것을 뜻한다.

A_i와 B_i가 가리키는 문자열이 다르다는 사실은 보장된다.

또한, (A_i, B_i)와 (B_i, A_i)의 연산 결과가 다를 수도 있다는 사실을 주의하자.

어떤 문자열의 '팰린드롬 점수'는,

해당 문자열에서 찾을 수 있는 서로 다른 부분 문자열 중에서 팰린드롬인 것의 개수로 정의한다.

여기서 문자열의 부분문자열이란, 문자열의 앞과 뒤에서 적당한 개수만큼 문자를 삭제하고 남은 문자열이다.

원소를 합치는 연산을 할 때마다, 합쳐진 문자열에 대한 팰린드롬 점수를 구하여라.

[Subtask]

#1 (9점) : N<=100

#2 (19점) : N<=1000

#3 (29점) : 모든 A_i, B_i에 대해 A_i= 1, B_i= i+1이다.

#4 (43점) : 제한 없음

팰린드롬 놀이 timer 1초 memory 1024MB

팰린드롬 놀이 1초 1024MB