After defeating so many castles, you are given the Water Stone, Thunder Stone, and Fire Stone. So don't worry, you'll get it eventually. (They are also sold by Traveling Merchants)
Hope this helps! •^-^•
A Traveling Merchant will come by and offer to sell one to you. The price is 5,000 coins, I think.
Keji the guy who gives you advice will give it to you after you beat either illusio or terra.