Apparently, sandstone takes FAR less time to form than most people think. Apparently, some sandstone deposits have been found with roman artefacts inside. They were normal sand at the time and turned to sandstone since then.

Basically, it would take far less time than you would think to form sandstone on Mars. It’s still proof of liquid water, but the lower end of the time estimate can be FAR shorter than you first think.