problem : https://atcoder.jp/contests/abc173/tasks/abc173_d

IMHO the proof in editorial is insufficient.

"IF the k+1-st person does not cut in to next to k-th person, then whether or not swapping them is none of their business." but it can have influence on people arrived after them.

Here is my proof not depends on people arrived in the decreasing order. Consider all the n-1 comfort we can get. I will prove: If there are k numbers >= x, others < x, then among all comfort we can get, there are at most 2*k-1 comfort >= x.

We note these k person as nice person, and the position between 2 nice person as nice position. also we note comfort >= x as nice comfort. 1. There are at most k-1 nice comfort we can get when these k nice person arrive(first nice person can not get nice comfort). 2. when a nice person arrive, nice position will increase at most one, when a not so nice person get a nice comfort, he must decrease a nice position. so not so nice persons can get k nice comfort at most.

so we can get at most 1 comfort >= a[0], 3 comfort >= a[1], and so on...