Description

An equilateral triangle with side length $n$ can be partitioned into $n^2$ small equilateral triangles of side length $1$, called unit triangles. An equilateral triangle with side length $3$ is divided into three layers for a total of $9$ small triangles, which we number $1\sim 9$ from top to bottom and left to right; see the figure below.

Four such equilateral triangles of side length $n$ can form a regular tetrahedron. We number the three side faces of the tetrahedron, in clockwise order as seen from top to bottom, as $A, B, C$, and the base as $D$. On side faces $A, B, C$, triangle $1$ has the tetrahedron’s apex as its top vertex; on the base face $D$, triangle $1$ has as its top vertex the point where it meets faces $A$ and $B$.

Here, $\tt .$ marks the position of triangle $1$ on that face, and the rest are numbered in order accordingly.

The above is the unfolded net of the tetrahedron. The dotted point on each face marks that face’s top vertex. Folding side faces $A, B, C$ inward reconstructs the tetrahedron. We partition each face $A, B, C, D$ into $n^2$ unit triangles.

Two unit triangles are adjacent if they share an edge. Clearly, each unit triangle has three adjacent unit triangles. Now, place all integers from $1$ to $4n^2$ randomly into the $4n^2$ unit triangles across the four faces, one number per unit triangle.

You are to compute the maximum binary search tree formed by unit triangles. The maximum binary search tree is the one with the largest number of nodes among all binary search trees formed by unit triangles. The requirement is that when $i$ is a node of the binary search tree, its children (if any) and its parent (if any) must be adjacent to $i$ by a shared edge in the folded tetrahedron (not adjacency in the unfolded net).

A binary search tree satisfies that every value in a node’s left subtree is strictly less than that node’s value, and every value in the right subtree is strictly greater than that node’s value.

Input Format

The first line contains an integer $n$, the side length of each triangular face in the unfolded net, i.e., each face has $n^2$ unit triangles.

Then follow four lines, each containing $n^2$ integers: the first line gives the numbers on face $A$, the second on face $B$, and so on.

Output Format

Output a single integer, the number of nodes in the maximum binary search tree.

3 
19 33 32 31 29 3 5 4 30 
22 25 20 21 12 24 23 34 35 
14 13 15 26 18 17 8 16 27 
11 10 9 1 28 7 2 6 36

17

Hint

Sample explanation

Take face $A$ as an example. Let $f(A, x)$ denote the $x$-th unit triangle on face $A$, and similarly for other faces.

$f(A,9)$ is adjacent to $f(D,1)$, $f(A,7)$ is adjacent to $f(D,2)$, and $f(A,5)$ is adjacent to $f(D,5)$.

$f(A,1)$ is adjacent to $f(B,1)$, $f(A,4)$ is adjacent to $f(B,2)$, and $f(A,9)$ is adjacent to $f(B,5)$.

$f(A,1)$ is adjacent to $f(C,1)$, $f(A,2)$ is adjacent to $f(C,4)$, and $f(A,5)$ is adjacent to $f(C,9)$.

Taking the number $1$ as the root, one maximum binary search tree is:

Constraints

For $100\%$ of the testdata, $1\leqslant n\leqslant 18$. All numbers on the four faces are distinct and are drawn from $[1,4n^2]$.

Translated by ChatGPT 5