\(N\) を \(\displaystyle \binom{N}{3} > K\) となる最小の値に設定します。

数列 \(B\) を次のように定義します。

• \(B_{\frac12(i-1)(i-2)+j}=|A_i-A_j|\) \((1 \leq j < i \leq N-1)\)

\(A_1, A_2, \ldots, A_{N-1}\) を次の条件を満たすように設定します。

• \(B\) の任意の \(2\) 要素が異なる
• 任意の \(i, j, k\) \((1 \leq i < j < k \leq N-1)\) について、 \(3\) 辺の長さが \(A_i, A_j, A_k\) の面積が正の三角形が存在する

この問題の制約では、例えば \(A_i = 10^{18} - i^5\) と設定するとこの条件を満たします。

そして、 \(A_N\) を \(B\) の要素のうち \(\displaystyle K-\binom{N-1}{3}+1\) 番目に小さい値に設定します。

この時、数列 \(A\) は条件を満たしていることが分かります。

計算量は \(O(N^2)\) です。

実装例 (C++, 36ms)