No need for scanf/printf, just do cin.sync_with_stdio(false) and get 0.5 seconds with 13 lines of code (hint: use deque).