Red Sandstone generates around surface aquifers in badlands biomes. It does not generate underneath red sand but it surrounds the edge of aquifers that are close enough to the surface to have terracotta touching them. It also generates around badlands mineshafts that pass through red sand. I believe this is supposed to be orange terracotta instead of red sandstone.

Images are from -3692434831046939593 but any seed will display this behavior.