https://mirror.codeforces.com/contest/1580/submission/130368106
The main idea is to choose the most optimal one number in every step.
UPD: To avoid unnecessary inconvenience, if you want to see a cute comic, click here , and please try to solve my problem.