Although (at least the right) stone is almost certainly a pretty good answer in general. There are plenty of historical examples and I'm skeptical that anything else exposed to the elements would do better. And if not exposed to the elements that feels like cheating.

Fair, but the sandstone and clay in that area is generally pretty awful. TBH most of the ancestral Puebloan structure are crumbling apart despite being protected by overhanging rock "roofs".

You're right about the pueblos specifically. They're still extant mostly because the climate is so dry there.

Something like granite would be a much more long-lived structural material in wetter climates. Indeed that's the primary stone used in, say, Machu Picchu.

It depends on whether they are occupied or not. I worked on an upstate New York farm with a barn that was post and beam, with a stone foundation. It was ~350 years old but had a good roof for that entire time.