The basic problem is atmospheric haze, which results in elevated black level of distant objects. For example, here is your first picture as you show it:
Here it is simply with the darkest part made black and the lightest white:
That's already better, but here the problem is that the darkest area was in the foreground. The foreground therefore looks well adjusted for, but the atmospheric haze still makes the background look washed out.
The best way to deal with that is selective masking and applying different adjustments to different parts of the picture. In this case I'd at minimum use different masks for the foreground rock, and the much more distant background behind it.
That's more work than I want to do here now. However, here is the black and white levels adjusted for the near part of the background at right:
Since I didn't do any masking this is also applied to the foreground, which now looks unnatural. It also points out a problem with haze and large distance ratio, which is that you can only correct for the haze at one distance.
The haze is "cancelled" at the hill at right, but is now even more obvious for the more distant parts. This is a real problem with haze.
Even basic and "free" corrections work on your second picture. Here is your original:
And here it is with the darkest part black and lightest part white:
As expected, the foreground looks un-hazed, but the background is still hazy. That's because it is hazy. Some haze actually helps to show depth. You can bring the overall black level down some more. Without masking, this trades off making the foreground look unnatural while making the background less hazy. Here is one such tradeoff that's not too bad (in my opinion):