2023 年上海市大学生程序设计竞赛 - 七月赛

在火星上居住着火星人，火星人有 $n$ 种性别 $1,2,3\dots n$ 且 $n$ 是偶数。因为火星的环境越来越恶劣了，他们想润到地球生活。为了办理地球签证，他们不得不将 $n$ 种性别分成”男性”和”女性”。其实火星人并不在意自己会被分为”男性”或者”女性”，他们在意的事情是:

• 彰显男女平等。这 $n$ 种火星人要平分为 $\frac n 2 $ 个男性，$\frac n 2$ 个女性。
• 尊重民族多样性。第 $i$ 种火星人和 第 $\lfloor \frac i 2 \rfloor$ 种火星人被分为相同性别时，会产生 $d_i$ 的多样性。火星人希望最大化多样性之和。

作为地球驻火星总领事馆大使，这个任务自然交到了你的手里。请你将这 $n$ 种火星人平分为男性和女性，并且最大化多样性之和。你只需要输出最大的多样性之和的值即可。