Educational Codeforces Round 58 F Trucks and Cities

https://codeforces.com/contest/1101/problem/F


The following solution is faster than mine. It is based on the fact that the prefix maximum doesn't change at most O(log N) times.
https://codeforces.com/blog/entry/64438?#comment-483640

There is an articles about this fact.
https://codeforces.com/blog/entry/62602

My solution is also used randomization, but it is not based on another fact.

If for all i we do binary search, time is not enough. So we first pick i randomly, and then find the answer only for it. Then, the answers of almost half of i s is less than this answer, so we can remove them. Repeat this thing, this action doesn't happen in O(log n) times.

But we got TLE. Sampling 10 elements instead of single element, finally I got AC.
https://codeforces.com/contest/1101/submission/48256161