Icons in the Toolbar

Gunnar is writing his own graphics editor because the drawing tools he has for LaTeX do not do what he wants. He drew an icon for every function of the editor, and every icon is a square image. The icons go into a toolbar with 2 rows and $N$ columns, one icon per cell.

The height of a row is the size of the largest icon in that row. The width of a column is the size of the largest icon in that column. The height of the toolbar is the sum of the heights of the two rows, and the width of the toolbar is the sum of the widths of the $N$ columns. The area of the toolbar is its height times its width.

For instance, in the arrangement below the height is $100 + 3$ and the width is $100 + 99 + 98$, so the area is $(100 + 3) \times (100 + 99 + 98) = 30591$.

You are given the sizes $s_1, s_2, \dots, s_{2N}$ of the $2N$ icons in non-increasing order. Icon $i$ is a square with side $s_i$. Place all of the icons in the toolbar so that the area is as small as possible, and report that area.

The first line contains one integer $N$ ($1 \le N \le 10^6$).

Each of the next $2N$ lines contains one integer $s_i$, the size of one icon. The sizes are given in non-increasing order, and $10^6 \ge s_1 \ge s_2 \ge \dots \ge s_{2N} \ge 1$.

Print one integer, the smallest possible area of the toolbar.