Isn't `a=a[2:]` going to copy and make that linear time too? I'm surprised he caught the `b.pop(0)` bug but then suggested doing that afterwards.
Also he should submit to codeforces to get a comparable running time. For example here is a random person who submitted AlphaCode's version and it takes 1091 ms https://codeforces.com/contest/1553/submission/144971343