首先，两个部分分别交互上界是 $n-1$，但是显然不能同时跑满。

其次，根据摩尔投票法的性质以及添加一些奇怪的记忆化，可能能够进一步减少交互次数？

感觉这个还可以继续加强，但是不是很会搞这个下界是多少……