Inconsistent type inference in closures

I'm having trouble understanding why Rust sometimes can and sometimes can't infer closure parameter types. I wrote a short demo of the problematic case (playground):

fn main() {
    bar(|x| x);
    bar(|x| !x); // Requires type annotation on x

trait Foo<T> {
    type Output;

impl<F: Fn(T) -> O, T, O> Foo<T> for F {
    type Output = O;

fn bar(_: impl Foo<bool, Output = bool>) {}

Why does the second case require type annotation?

The reasoning for inference seem the same (bar needs Foo with bools, only closure with bools implements Foo with bools, closure must be bool -> bool), but somehow the negation operation breaks it all. I understand that the Not trait makes relation between input and output unclear, because negation of type A could be type B, but here both input and output are strictly defined by impl Foo for Fn.