시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 11 3 2 40.000%

문제

그래프를 주어진 제약조건을 만족하도록 평면상에 그리는 것은 VLSI에서 회로를 배선하거나 정보 시스템의 구조를 다이어그램으로 나타내어 분석하는데 이용된다. 이 문제에서는 주어진 이진트리(binary tree)를 다음 조건을 만족하도록 이차원 격자구조에 그리는 문제를 고려한다. 

  1. 루트는 격자상의 최상단 가장 왼쪽 모서리에 위치한다.
  2. 각 정점에 대해 하나의 자식 정점은 수평방향 오른쪽, 다른 자식 정점은 수직방향 아래쪽의 격자점에 위치한다 (자식정점이 하나인 경우는 둘중 하나의 조건을 만족).
  3. 각 정점에 대해 두 자식 정점을 루트로 하는 서브트리를 둘러싼 두 직사각형은 서로 겹치지 않는다.

예를 들어, 다음은 주어진 이진트리를 위의 제약 조건을 만족하도록 그린 것이다.

왼쪽부터 이진트리, 그리기-1, 그리기-2, 그리기-3이다.

또, 위와 같이 이진 트리를 그릴 때는 그리기에 필요한 면적이 중요한 평가 요소가 된다. 어떤 그리기의 면적은 그리기에 필요한 이차원 격자의 가로크기와 세로크기를 곱한 값이다. 그러므로, 위의 그림에서 <그리기-1>의 면적은 16이며 <그리기-2>와 <그리기-3>의 면적은 15이다.
이진 트리가 주어질 때 위의 제약 조건을 만족하는 그리기 중 면적을 최소로 하는 그리기의 면적을 출력하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 이진트리의 정점수를 나타내는 n이 주어진다(1≤n≤100). 둘째줄에는 n개의 정수로 구성된 수열이 주어진다. 주어지는 정수 수열은 이진트리를 전위(preorder) 순회한 순서가 1, 2, 3, . . . ,n 이라고 가정했을 때, 그 이진트리를 중위순회한 순서를 나타낸다. 정수 사이에는 빈칸이 하나 있다. 올바른 입력만 주어진다고 가정한다.

출력

첫 줄에 최소 면적을 출력한다.

예제 입력

9
4 3 5 2 6 1 8 7 9

예제 출력

12

힌트