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

IMHO the proof in editorial is insufficient.

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...