The simple interpretation of PAO's UHECRs' penetration depth measurements suggests a transition at the energy range $1.1 - 35 \cdot 10^{18} $ eV from protons to heavier nuclei. A detailed comparison of this data with air shower simulations reveals strong restrictions on the amount of light nuclei (protons and He) in the observed flux. We find a robust upper bound on the observed proton fraction of the UHECRs flux and we rule out a composition dominated by protons and He. Acceleration and propagation effects lead to an observed composition that is different from the one at the source. Using a simple toy model that take into account these effects, we show that the observations requires an extreme metallicity at the sources with metals to protons mass ratio of 1:1, a ratio that is larger by a factor of a hundred than the solar abundance. This composition imposes an almost impossible constraint on all current astrophysical models for UHECRs accelerators. This may provide a first hint towards new physics that emerges at $\sim 100$ TeV and leads to a larger proton cross section at these energies.