آرایه $a_1, a_2,\dots , a_n$ شامل $n$ عدد صحیح متمایز است. عدد رنگی این آرایه کوچکترین عدد طبیعی مثل $C$ است که بتوان با $C$ رنگ، مجموعه اعداد صحیح را رنگ کرد طوری که شرط زیر برقرار باشد:

برای هر $i$ و $j$ که $1 \leq i < j \leq n$ و هر $x$ صحیح دلخواه، رنگ دو عدد $a_i + x$ و $a_j + x$ متفاوت باشد.

می‌خواهیم با تعدادی عملیات کاری کنیم که عدد رنگی آرایه کمتر یا مساوی $n$ شود. در هر عملیات می‌توانیم یکی از دو کار زیر را انجام دهیم.

• یکی از اعضای آرایه را به علاوه ۱ کنیم.
• یکی از اعضای آرایه را منهای ۱ کنیم.

ثابت کنید با کمتر یا مساوی $\lfloor \frac{n^2}{4} \rfloor$ عملیات می‌توانیم به خواسته‌مان برسیم. دقت کنید در طی عملیات‌ها ممکن است بعضی از اعضای آرایه برابر شوند، اما در انتها تمامی اعداد باید متمایز باشند.
در صورتی که ثابت کنید با کمتر یا مساوی $\lfloor \frac{n^2}{2} \rfloor$ عملیات نیز می‌توانیم به خواسته‌مان برسیم، ۲۵ امتیاز دریافت می‌کنید.

• سوال قبل