410643: GYM104068 H Toxel 与宝可梦对战特训

Memory Limit:0 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Toxel 与宝可梦对战特训time limit per test1 secondmemory limit per test1024 MBinputstandard inputoutputstandard output

Toxel 正在带领它的宝可梦进行对战的特训。Toxel 有 n 只宝可梦,它们的编号为 。宝可梦们需要打 n 场对战,每场对战由两只宝可梦参加,其中一只为攻击方,另一只为防御方。每只宝可梦需要作为攻击方和防御方各参加恰一场对战。显然一只宝可梦不能同时作为攻击方和防御方参加同一场对战。

i 只宝可梦具有属性 ai,不同属性的宝可梦进行对战会产生不同的疲劳值。第 i 只和第 j 只宝可梦进行的对战会产生 ai·aj 的疲劳值。Toxel 不希望它的宝可梦太累,因此它希望合理安排对战,使得 n 次对战产生的疲劳值的最大值最小

形式化地说,给定一个长度为 n 的数列 a,你需要求出一个排列 p,使得对所有 i,有 pi ≠ i,且 max{ai·api} 最小。

Input

第一行一个整数 n2 ≤ n ≤ 105),表示宝可梦的数量。

第二行 n 个整数 a1, a2, ..., an1 ≤ ai ≤ 109),表示每只宝可梦的属性。

Output

一行一个整数,表示最小值。

ExamplesInput
3
1 2 3
Output
6
Input
6
1 1 4 5 1 4
Output
5

加入题单

上一题 下一题 算法标签: