Comments

and to my surprise, it even faster than most of O(nlogn) solutions.

Maybe testdata of F1 and F2 is too weak? My O(n^2) solution for F1 successfully passed F2. https://mirror.codeforces.com/contest/1844/submission/213394774