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第一行一个整数 n(2 ≤ n ≤ 105),表示宝可梦的数量。
第二行 n 个整数 a1, a2, ..., an(1 ≤ ai ≤ 109),表示每只宝可梦的属性。
Output一行一个整数,表示最小值。
ExamplesInput3 1 2 3Output
6Input
6 1 1 4 5 1 4Output
5