本题不建议写 SA

警钟砸烂。受害者发帖。

这玩意虽然是单 log 常数也不算特别大，但是 Codeforces 的垃圾评测机和高强度数据能够把你的代码创飞。

老老实实写线性做法吧。