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

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

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

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

第一行一个整数 n（2 ≤ n ≤ 10⁵），表示宝可梦的数量。

第二行 n 个整数 a₁, a₂, ..., a_n（1 ≤ a_i ≤ 10⁹），表示每只宝可梦的属性。

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

3
1 2 3

6

6
1 1 4 5 1 4

5