The ArrayDeque documentation mentions:

Append, prepend, removeFirst, removeLast and random-access (indexed-lookup and indexed-replacement) take amortized constant time.

However, removeFirst is defined as: def removeFirst(p: A => Boolean, from: Int): Option[A] (which obviously won't take constant time).
This should have been removeHead, which mirrors removeLast (including the *Option and *While variants).