Actually, a lot of the sandstone in Monument Valley and Canyonlands (certainly, the most impressive buttes and mesas) isn’t marine, but aeolian. Fossilized dunes, basically. Much of the rest is river sandbar and alluvial fan deposits, and then the rest is delta and coastal sandbar sands.
Generally, when you have a lot of reddish-orangish sandstone, it’s not primarily marines, but terrestrial.