> FYI Raymond, your revision 0731f097157b didn’t actually merge the 3.5 branch (It only had one parent). Also, the default branch never got any NEWS entry in 58266f5101cc, so maybe it needs to be added?

Maybe it's also worth to document the change in Python 3.5 and 3.6 documentation with a ".. versionchanged::"?
https://docs.python.org/dev/library/collections.html#deque-objects

It can be suprising to get a different behaviour between two bugfix versions (Python 3.5.1 and 3.5.2). I'm not saying that we must not fix bugs, just that it helps users to document them :-)

It will also avoid bug reports about this behaviour change. Example of user report: issue #26260, "it works on Python 2 but no more on Python 3" ;-)