high i did world challenge last summer and it was amazing, i was fine fitness wise but i literally started going to the gym 1 month ago and now my biggest regret is doing NO training for it because it would have helped. so well done for that..
anyway, cycling/swimming are good... swimming is really good for breathing as well as cardio so should help you high altitude... also if you live near the beach running on sand is supposed to be good.