As I said, Polynesia. I can't make a good story, thus I post it as a guide. Spoiler : Discover polytheism (pantheon) and then priesthood. You need to discover priesthood early for the malai. Starting situation: Mua for New Zealand and Niue for easter island. Note, that Mua controls its fat cross, cause it is the settler farm. Then discover masonry (moai status).