Paranoid String
Contest: Codeforces Round 800 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, greedy

Let's call a binary string $$$T$$$ of length $$$m$$$ indexed from $$$1$$$ to $$$m$$$ paranoid if we can obtain a string of length $$$1$$$ by performing the following two kinds of operations $$$m-1$$$ times in any order :

- Select any substring of $$$T$$$ that is equal to 01, and then replace it with 1.
- Select any substring of $$$T$$$ that is equal to 10, and then replace it with 0.For example, if $$$T = $$$ 001, we can select the substring $$$[T_2T_3]$$$ and perform the first operation. So we obtain $$$T = $$$ 01.

You are given a binary string $$$S$$$ of length $$$n$$$ indexed from $$$1$$$ to $$$n$$$. Find the number of pairs of integers $$$(l, r)$$$ $$$1 \le l \le r \le n$$$ such that $$$S[l \ldots r]$$$ (the substring of $$$S$$$ from $$$l$$$ to $$$r$$$) is a paranoid string.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of $$$S$$$.

The second line of each test case contains a binary string $$$S$$$ of $$$n$$$ characters $$$S_1S_2 \ldots S_n$$$. ($$$S_i = $$$ 0 or $$$S_i = $$$ 1 for each $$$1 \le i \le n$$$)

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the number of pairs of integers $$$(l, r)$$$ $$$1 \le l \le r \le n$$$ such that $$$S[l \ldots r]$$$ (the substring of $$$S$$$ from $$$l$$$ to $$$r$$$) is a paranoid string.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, $$$S$$$ already has length $$$1$$$ and doesn't need any operations.

In the second sample, all substrings of $$$S$$$ are paranoid. For the entire string, it's enough to perform the first operation.

In the third sample, all substrings of $$$S$$$ are paranoid except $$$[S_2S_3]$$$, because we can't perform any operations on it, and $$$[S_1S_2S_3]$$$ (the entire string).

Example input:
5
1
1
2
01
3
100
4
1001
5
11111

Example output:
1
3
4
8
5

Editorial:
We want to show that a binary string $$$T$$$ of length $$$m$$$ is paranoid if and only if $$$m = 1$$$ or ($$$1 < m$$$ and $$$S[m] \neq S[m - 1]$$$).
• In the case of $$$S[m - 1] = S[m]$$$: We can never delete the last two characters because they will always remain equal. So $$$S$$$ is not paranoid.
• In the case of $$$S[m - 1] \neq S[m]$$$: If $$$m = 2$$$, we can reach our goal by one operation. Otherwise assume that the last character is 0. Now the last three characters are either 010 or 110. In the first case perform the operation on $$$[S_{m-2},S_{m-1}]$$$ and in the second case perform the operation on $$$[S_{m-1},S_m]$$$. Then the last two characters will be 10 and we can continue this algorithm on the new string until we reach $$$m = 1$$$.
The number of paranoid substrings of length $$$1$$$ is equal to $$$n$$$. To count the number of longer substrings, we can fix $$$r$$$ from index $$$2$$$ to $$$n$$$. if $$$S[r] \neq S[r - 1]$$$ holds, we should add $$$r - 1$$$ to the answer.
complexity: $$$\mathcal{O}(n)$$$