Lonely Photos

Farmer John recently purchased \(N\) new cows (\(3 \le N \le 5 \times 10^5\)), each of which is either a Guernsey or a Holstein. The cows are arranged in a row. For every contiguous sequence of at least three cows, Farmer John takes a photo. However, he discards any photo in which exactly one cow is of one breed (i.e. exactly one Guernsey or exactly one Holstein), believing that the unique cow would feel isolated.

Your task is to compute the number of photos that will be discarded. Two photos are considered different if they start or end at different positions in the row.

Note: A photo (a contiguous subarray) is discarded if it contains exactly one occurrence of either Guernsey or Holstein. In other words, if a subarray of length \(L\) (with \(L \ge 3\)) contains either \(\text{count}_G = 1\) (and \(\text{count}_H = L-1\)) or \(\text{count}_H = 1\) (and \(\text{count}_G = L-1\)), then it is considered a lonely photo.

inputFormat

The first line contains an integer \(N\) (the number of cows). The second line contains a string of length \(N\) consisting only of characters 'G' and 'H', representing the breed of each cow in order.

outputFormat

Output a single integer, the number of photos that Farmer John discards.

sample

3
GHH

1