{
  "$schema": "https://schema.management.azure.com/schemas/2015-01-01/deploymentTemplate.json#",
  "contentVersion": "1.0.0.0",
  "parameters": {
    "newStorageAccountName": {
      "type": "string",
      "metadata": {
          "description": "Name of the Storage Account"
      }
    },
    "location": {
      "type": "string",
      "allowedValues": ["West US", "West Europe", "Southeast Asia"],
      "metadata": {
          "description": "Location of Premium storage account"
      }
    }
  },
  "resources": [
    {
      "type": "Microsoft.Storage/storageAccounts",
      "name": "[parameters('newStorageAccountName')]",
      "apiVersion": "2015-05-01-preview",
      "location": "[parameters('location')]",
      "properties": {
        "accountType": "Premium_LRS"
      }
    }
  ]
}

{
  "$schema": "https://schema.management.azure.com/schemas/2015-01-01/deploymentTemplate.json#",
  "contentVersion": "1.0.0.0",
  "parameters": {
    "newStorageAccountName": {
      "type": "string",
      "metadata": {
          "description": "Name of the Storage Account"
      }
    },
    "location": {
      "type": "string",
      "allowedValues": ["West US", "West Europe", "Southeast Asia", "East China", "West Japan", "Australia East", "East US 2"],
      "metadata": {
          "description": "Location of Premium storage account"
      }
    }
  },
  "resources": [
    {
      "type": "Microsoft.Storage/storageAccounts",
      "name": "[parameters('newStorageAccountName')]",
      "apiVersion": "2015-05-01-preview",
      "location": "[parameters('location')]",
      "properties": {
        "accountType": "Premium_LRS"
      }
    }
  ]
}

Update regions that support premium storage
Update regions that support premium storage

According to https://azure.microsoft.com/en-us/documentation/articles/storage-premium-storage-preview-portal/
Premium Storage is currently available in the following regions: West US, East US 2, West Europe, East China, Southeast Asia, West Japan and Australia East.