Покажемо, що оптимальне парування для даного масиву — це об'єднати в пари (1, 1+\frac{n+1}{2}), (2, 2+\frac{n+1}{2}), \ldots, (1+\frac{n+1}{2}, n+1). Будемо позначати парування як \frac{n+1}{2} пар (l_i, r_i), де 1\le l_i<r_i\le n+1, і кожне число від до n+1 зустрічається рівно один раз як l_i чи r_i.
Для цього розглянемо парування з найбільшою сумарною вагою ребер, серед них — з найбільшою сумою |r_i-l_i|, а серед них — з найменшою сумою |r_i-l_i|^2.
Якщо є дві пари (l_i, r_i) і (l_j, r_j), що не перетинаються, тобто l_i<r_i<l_j<r_j, то вигідно замінити їх на (l_i, l_j), (r_i, r_j). Сумарна вага ребер не зменшиться, а сума |r_i-l_i| збільшиться.
Якщо є дві пари (l_i, r_i) і (l_j, r_j), одна з яких містить іншу, тобто l_i<l_j<r_j<r_i, то вигідно замінити їх на (l_i, r_j), (l_j, r_i). Можна показати, що сумарна вага ребер не зменшиться, сума |r_i-l_i| не зміниться, а сума |r_i-l_i|^2 зменшиться.
Таким чином, маємо що в такому паруванні кожні два ребра перетинаються, але не містять одне одного. Єдине таке парування приведено в першому реченні.
Лишилось знайти суму \sum_{1\le t \le \frac{n+1}{2}} max(a_t, a_{t+1}, \ldots, a_{t+\frac{n+1}{2}-1}). по всім перестановкам даного масиву. Для цього досить знайти маточікування \sum_{1\le t \le \frac{n+1}{2}} max(a_t, a_{t+1}, \ldots, a_{t+\frac{n+1}{2}-1}) по випадковій перестановці даного масиву. Очевидно, що маточікування цього однакове для всіх , тому лишилось знайти маточікування максимуму випадково вибраної підмножини з x = \frac{n+1}{2} елементів. Це вже зробити простіше: для -го елементу в порядку зростання ймовірність того, що він буде максимумом, рівна \frac{C(i-1, t-1)}{C(n, t)}, а отже вклад в маточікування рівний a_i\frac{C(i-1, t-1)}{C(n, t)}.