C - Make a Rectangle

Contest Duration: 2017-08-20(Sun) 12:00 - 2017-08-20(Sun) 13:40 (local time) (100 minutes) Back to Home

C - Make a Rectangle Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $300$ 点

問題文

太さが無視できる棒が $N$ 本あります． $i$ 番目の棒の長さは $A_i$ です．

すぬけ君は，これらの棒から $4$ 本の異なる棒を選び，それらの棒を辺として長方形（正方形を含む）を作りたいです．作ることができる最大の長方形の面積を求めてください．

制約

$4 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$A_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$  ...  $A_N$

出力

すぬけ君が作ることのできる最大の長方形の面積を出力せよ．ただし，長方形を作れない場合は， $0$ を出力せよ．

入力例 1Copy

Copy

6
3 1 2 4 2 1

出力例 1Copy

Copy

$1 \times 2$ の長方形を作ることができます．

入力例 2Copy

Copy

4
1 2 3 4

出力例 2Copy

Copy

長方形を作ることはできません．

入力例 3Copy

Copy

10
3 3 3 3 4 4 4 5 5 5

出力例 3Copy

Copy

Score : $300$ points

Problem Statement

We have $N$ sticks with negligible thickness. The length of the $i$ -th stick is $A_i$ .

Snuke wants to select four different sticks from these sticks and form a rectangle (including a square), using the sticks as its sides. Find the maximum possible area of the rectangle.

Constraints

$4 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$A_i$ is an integer.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $A_2$  ...  $A_N$

Output

Print the maximum possible area of the rectangle. If no rectangle can be formed, print $0$ .

Sample Input 1Copy

Copy

6
3 1 2 4 2 1

Sample Output 1Copy

Copy

$1 \times 2$ rectangle can be formed.

Sample Input 2Copy

Copy

4
1 2 3 4

Sample Output 2Copy

Copy

No rectangle can be formed.

Sample Input 3Copy

Copy

10
3 3 3 3 4 4 4 5 5 5

Sample Output 3Copy

Copy