Find element where 40% is less and 40% is greater in O(n)

You are given an unsorted array A of integers. Your task is to find an element e such that at least 40% of all elements are smaller than or equal to e and at least 40% of all elements are larger than or equal to e. Devise an algorithm that outputs such an element e with probability at least 1/2, and otherwise just outputs “failure”. The algorithm is supposed to have linear running time (in the worst case).

Stupid approach:

Insert: A
with probability > 1/2 do:
    m = median of median(A)    O(n)
    check if constrain holds   O(n) using simple count 
    holds? 
        return m
    holds not
        return Failure
else:
    return Failure

There must be a smarter approach!