@DJ... I stayed in the Red Lion in Fareham.... I payed around 52 euro, was breakfast included and you could use the local gym centre that was about 2min walking distance away for free as well during your stay which I liked since it gave me something to do the day before... I made my booking via laterooms.com I think.
You could find a few places that were just a bit cheaper but they were all a quite a bit further away or completely booked at that time...
I thought the Red Lion was not to bad and not to far away from nats.