ヒント → https://atcoder.jp/contests/arc158/editorial/5901

---

調べる値は \(i, j, k\) について対称なので， \(1≤i<j<k≤N\) という順序は忘れて，単に相異なる \(3\) 数を選ぶ問題として考えます．

また，列 \(x\) には同じ値が複数回含まれる可能性がありますが，同じ値にも適当な順位をつけて，「大きい方から \(k\) 番目」というようなものがちょうどひとつの要素を指すことにして議論します．

---

[1] 最適解の絞り込み

まずは簡単な場合として，\(x_i, x_j\) が既に選ばれているときに最適な \(x_k\) がどのようなものかを考えましょう．

この場合，\(a = x_i + x_j\), \(b = x_ix_j\) とおけば，調べるべき値は

\[\frac{x_i+x_j+x_k}{x_ix_jx_k} = \frac{a+x_k}{bx_k} = \frac{a}{b}\cdot \frac{1}{x_k} + \frac{1}{b}\]

と書くことができます．したがって，この値が最大・最小になるのは，\(1/x_k\) が最大または最小である場合のどちらかだとわかります（\(a,b\) の符号により，目的関数の最大・最小値が\(1/x_k\) の最大・最小値のどちらに対応するかは変化しますが，\(1/x_k\) の最大値・最小値を調べれば十分であるという点は共通しています）．

既に選ばれた \(x_i, x_j\) のことをも考慮しても，\(x_k\) としては，列全体の中で \(1/x_k\) が小さい方・大きい方から \(1, 2, 3\) 番目にあるもののみを考えれば十分であることが分かります．

---

[2] 解法

もとの列 \(x\) のうちで，\(1/x_i\) が小さい方または大きい方から \(1,2,3\) 番目にあるものからなる多重集合を \(X\) とします．

最適解を考える上で，\(x_k \in X\) であるもののみを調べればよいことが分かりました．同様に，\(x_i, x_j\in X\) も成り立つもののみを調べればよいことが分かります．

したがって，本問題は次のようにして解くことができます．

• 列 \(x\) を \(1/x_i\) について昇順になるようにソートする．先頭 \(3\) 項または末尾 \(3\) 項に含まれる要素からなる多重集合を \(X\) とする．
• \(X\) から \(3\) 数を選ぶ方法をすべて試して，それらの最小値・最大値を出力する．

\(1/x_i\) に関してソートする部分では，実際に \(1/x_i\) の値を計算してもよいですし，もとの列 \(x\) について，「負の数を降順に並べ，正の数を降順に並べてそれらを連結する」という操作を行うこととして実装することもできます．

この解法の時間計算量は \(O(N\log N)\) です．なお，列全体のソートは不要で上位・下位 3 件だけを選択できればよいので，\(O(N)\) 時間で解くこともできます．

---

なお [1] の考察をより推し進めると，\(1/x_i\) を昇順に並べたときの先頭 \(3\) 項を \((a_1,a_2,a_3)\)，末尾 \(3\) 項を \((b_1,b_2,b_3)\) とするとき，次の \(4\) 通りの値のみを調べればよいことも分かります：

• \((a_1,a_2,a_3)\)
• \((a_1,a_2,b_3)\)
• \((a_1,b_2,b_3)\)
• \((b_1,b_2,b_3)\)

ただし，ここの探索回数を \(\binom{6}{3}=20\) 通りから \(4\) 通りに減らすことは，ソートの前計算 \(O(N\log N)\) 時間を含む解法全体の高速化にはほとんど寄与しませんし，コンテスト中の戦略としても探索回数や実装量を十分少なく絞り込んだところまでで考察を止めてしまってよいと思います．