1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Minimise Oneness
Contest: Codeforces Round 979 (Div. 2)
Difficulty rating: 800
Tags: combinatorics, constructive algorithms, games, math

For an arbitrary binary string $$$t$$$$$$^{\text{∗}}$$$, let $$$f(t)$$$ be the number of non-empty subsequences$$$^{\text{†}}$$$ of $$$t$$$ that contain only $$$\mathtt{0}$$$, and let $$$g(t)$$$ be the number of non-empty subsequences of $$$t$$$ that contain at least one $$$\mathtt{1}$$$.

Note that for $$$f(t)$$$ and for $$$g(t)$$$, each subsequence is counted as many times as it appears in $$$t$$$. E.g., $$$f(\mathtt{000}) = 7, g(\mathtt{100}) = 4$$$.

We define the oneness of the binary string $$$t$$$ to be $$$|f(t)-g(t)|$$$, where for an arbitrary integer $$$z$$$, $$$|z|$$$ represents the absolute value of $$$z$$$.

You are given a positive integer $$$n$$$. Find a binary string $$$s$$$ of length $$$n$$$ such that its oneness is as small as possible. If there are multiple strings, you can print any of them.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The only line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of $$$s$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, output $$$s$$$ on a new line. If multiple answers exist, output any.

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

Note:
In the first test case, for the example output, $$$f(t)=1$$$ because there is one subsequence that contains only $$$\mathtt{0}$$$ ($$$\mathtt{0}$$$), and $$$g(t)=0$$$ because there are no subsequences that contain at least one $$$1$$$. The oneness is $$$|1-0|=1$$$. The output $$$\mathtt{1}$$$ is correct as well because its oneness is $$$|0-1|=1$$$.

For the example output of the second test case, $$$f(t)=1$$$ because there is one non-empty subsequence that contains only $$$\mathtt{0}$$$, and $$$g(t)=2$$$ because there are two non-empty subsequences that contain at least one $$$\mathtt{1}$$$ ($$$\mathtt{01}$$$ and $$$\mathtt{1}$$$). The oneness is thus $$$|1-2|=1$$$. It can be shown that $$$1$$$ is the minimum possible value of its oneness over all possible binary strings of size $$$2$$$.

Example input:
3
1
2
3

Example output:
0
01
010

Editorial:
A TRUE Battle
Contest: Codeforces Round 979 (Div. 2)
Difficulty rating: 1100
Tags: brute force, games, greedy

Alice and Bob are playing a game. There is a list of $$$n$$$ booleans, each of which is either true or false, given as a binary string $$$^{\text{∗}}$$$ of length $$$n$$$ (where $$$\texttt{1}$$$ represents true, and $$$\texttt{0}$$$ represents false). Initially, there are no operators between the booleans.

Alice and Bob will take alternate turns placing and or or between the booleans, with Alice going first. Thus, the game will consist of $$$n-1$$$ turns since there are $$$n$$$ booleans. Alice aims for the final statement to evaluate to true, while Bob aims for it to evaluate to false. Given the list of boolean values, determine whether Alice will win if both players play optimally.

To evaluate the final expression, repeatedly perform the following steps until the statement consists of a single true or false:

- If the statement contains an and operator, choose any one and replace the subexpression surrounding it with its evaluation.
- Otherwise, the statement contains an or operator. Choose any one and replace the subexpression surrounding the or with its evaluation.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the string.

The second line contains a binary string of length $$$n$$$, consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$ — the list of boolean values.

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

Output format:
For each testcase, output "YES" (without quotes) if Alice wins, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

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

Note:
In the first testcase, Alice can place and between the two booleans. The game ends as there are no other places to place operators, and Alice wins because true and true is true.

In the second testcase, Alice can place or between the middle true and the left false. Bob can place and between the middle true and the right false. The statement false or true and false is false.

Note that these examples may not be the best strategies for either Alice or Bob.

Example input:
5
2
11
3
010
12
101111111100
10
0111111011
8
01000010

Example output:
YES
NO
YES
YES
NO

Editorial:
MEXimize the Score
Contest: Codeforces Round 979 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, data structures, dp, greedy, implementation, math

Suppose we partition the elements of an array $$$b$$$ into any number $$$k$$$ of non-empty multisets $$$S_1, S_2, \ldots, S_k$$$, where $$$k$$$ is an arbitrary positive integer. Define the score of $$$b$$$ as the maximum value of $$$\operatorname{MEX}(S_1)$$$$$$^{\text{∗}}$$$$$$ + \operatorname{MEX}(S_2) + \ldots + \operatorname{MEX}(S_k)$$$ over all possible partitions of $$$b$$$ for any integer $$$k$$$.

Envy is given an array $$$a$$$ of size $$$n$$$. Since he knows that calculating the score of $$$a$$$ is too easy for you, he instead asks you to calculate the sum of scores of all $$$2^n - 1$$$ non-empty subsequences of $$$a$$$.$$$^{\text{†}}$$$ Since this answer may be large, please output it modulo $$$998\,244\,353$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < n$$$) — the elements of the array $$$a$$$.

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

Output format:
For each test case, output the answer, modulo $$$998\,244\,353$$$.

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

Note:
In the first testcase, we must consider seven subsequences:

- $$$[0]$$$: The score is $$$1$$$.
- $$$[0]$$$: The score is $$$1$$$.
- $$$[1]$$$: The score is $$$0$$$.
- $$$[0,0]$$$: The score is $$$2$$$.
- $$$[0,1]$$$: The score is $$$2$$$.
- $$$[0,1]$$$: The score is $$$2$$$.
- $$$[0,0,1]$$$: The score is $$$3$$$.

In the last testcase, all subsequences have a score of $$$0$$$.

Example input:
4
3
0 0 1
4
0 0 1 1
5
0 0 1 2 2
4
1 1 1 1

Example output:
11
26
53
0

Editorial:
Orangutan Approved Subarrays
Contest: Codeforces Round 979 (Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, dp, greedy, implementation, two pointers

Suppose you have an array $$$b$$$. Initially, you also have a set $$$S$$$ that contains all distinct elements of $$$b$$$. The array $$$b$$$ is called orangutan-approved if it can be emptied by repeatedly performing the following operation:

- In one operation, select indices $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq |b|$$$) such that $$$v = b_l = b_{l+1} = \ldots = b_r$$$ and $$$v$$$ is present in $$$S$$$. Remove $$$v$$$ from $$$S$$$, and simultaneously remove all $$$b_i$$$ such that $$$l \leq i \leq r$$$. Then, reindex the elements $$$b_{r+1}, b_{r+2}, \ldots$$$ as $$$b_l, b_{l+1}, \ldots$$$ accordingly.

You are given an array $$$a$$$ of length $$$n$$$ and $$$q$$$ queries.

Each query consists of two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), and you need to determine whether or not the subarray $$$a_{l}, a_{l+1}, \ldots, a_r$$$ is orangutan-approved.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 10^5$$$) — the size of $$$a$$$ and the number of queries, respectively.

The following line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array $$$a$$$.

The following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ — the endpoints of the subarray for each query ($$$1 \leq l \leq r \leq n$$$).

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, output "YES" (without quotes) if the subarray from $$$l$$$ to $$$r$$$ is orangutan-approved, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first query of the first testcase, the answer is YES.

- Initially, $$$S=\{1,2\}$$$ and $$$b=[1,2,2,1]$$$
- Select $$$l=2$$$ and $$$r=3$$$. Since $$$b_2=b_3=2$$$ is in $$$S$$$, we may erase $$$b_2$$$ and $$$b_3$$$ from the array, as well as erasing $$$2$$$ from $$$S$$$. The set $$$S$$$ becomes $$$\{1\}$$$ and the array becomes $$$[1,1]$$$.
- Select $$$l=1$$$ and $$$r=2$$$. Since $$$b_1=b_2=1$$$ is in $$$S$$$, we may erase $$$b_1$$$ and $$$b_2$$$ from the array, as well as erasing $$$1$$$ from $$$S$$$. The set $$$S$$$ becomes $$$\{\}$$$ and the array becomes $$$[]$$$.
- Since the array is now empty, we can say the original array is orangutan-approved.

In the first query of the second testcase, the answer is NO, because it can be shown that the subarray $$$[2,1,2,1]$$$ cannot become empty through any sequence of valid operations.

Example input:
3
4 2
1 2 2 1
1 4
1 3
5 3
1 2 1 2 1
2 5
3 5
1 3
8 4
1 2 3 2 1 3 2 3
1 5
2 8
3 5
6 8

Example output:
YES
YES
NO
YES
YES
YES
NO
YES
YES

Editorial:
Make All Equal
Contest: Codeforces Round 967 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

You are given a cyclic array $$$a_1, a_2, \ldots, a_n$$$.

You can perform the following operation on $$$a$$$ at most $$$n - 1$$$ times:

- Let $$$m$$$ be the current size of $$$a$$$, you can choose any two adjacent elements where the previous one is no greater than the latter one (In particular, $$$a_m$$$ and $$$a_1$$$ are adjacent and $$$a_m$$$ is the previous one), and delete exactly one of them. In other words, choose an integer $$$i$$$ ($$$1 \leq i \leq m$$$) where $$$a_i \leq a_{(i \bmod m) + 1}$$$ holds, and delete exactly one of $$$a_i$$$ or $$$a_{(i \bmod m) + 1}$$$ from $$$a$$$.

Your goal is to find the minimum number of operations needed to make all elements in $$$a$$$ equal.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of array $$$a$$$.

Output format:
For each test case, output a single line containing an integer: the minimum number of operations needed to make all elements in $$$a$$$ equal.

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

Note:
In the first test case, there is only one element in $$$a$$$, so we can't do any operation.

In the second test case, we can perform the following operations to make all elements in $$$a$$$ equal:

- choose $$$i = 2$$$, delete $$$a_3$$$, then $$$a$$$ would become $$$[1, 2]$$$.
- choose $$$i = 1$$$, delete $$$a_1$$$, then $$$a$$$ would become $$$[2]$$$.

It can be proven that we can't make all elements in $$$a$$$ equal using fewer than $$$2$$$ operations, so the answer is $$$2$$$.

Example input:
7
1
1
3
1 2 3
3
1 2 2
5
5 4 3 2 1
6
1 1 2 2 3 3
8
8 7 6 3 8 7 6 3
6
1 1 4 5 1 4

Example output:
0
2
1
4
4
6
3

Editorial:
Let $$$x$$$ be one of the most frequent elements in $$$a$$$, then the answer must be at least $$$(n - \text{frequency of } x)$$$, and this lower bound is always achievable by keep erasing a non-$$$x$$$ element from $$$a$$$, and we can prove it's always possible to do so.
proof:
Let $$$y$$$ denote any value that is not $$$x$$$, then $$$a$$$ would have the form $$$x \ldots x, y \ldots y, x \ldots x, \ldots$$$. Let's focus on the subarray $$$x, y \ldots y, x$$$. In this subarray, there must exist adjacent elements that satisfy $$$a_i \leq a_{(i \bmod m) + 1}$$$, otherwise we would have $$$x > y > \ldots > y > x$$$ implying $$$x > x$$$ which leads to a contradiction.
Shape Perimeter
Contest: Codeforces Round 997 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math

There is an $$$m$$$ by $$$m$$$ square stamp on an infinite piece of paper. Initially, the bottom-left corner of the square stamp is aligned with the bottom-left corner of the paper. You are given two integer sequences $$$x$$$ and $$$y$$$, each of length $$$n$$$. For each step $$$i$$$ from $$$1$$$ to $$$n$$$, the following happens:

- Move the stamp $$$x_i$$$ units to the right and $$$y_i$$$ units upwards.
- Press the stamp onto the paper, leaving an $$$m$$$ by $$$m$$$ colored square at its current position.

Note that the elements of sequences $$$x$$$ and $$$y$$$ have a special constraint: $$$1\le x_i, y_i\le m - 1$$$.

Note that you do not press the stamp at the bottom-left corner of the paper. Refer to the notes section for better understanding.

It can be proven that after all the operations, the colored shape on the paper formed by the stamp is a single connected region. Find the perimeter of this colored shape.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$2 \le m \le 100$$$) — the number of operations performed and the side length of the square stamp.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le m - 1$$$) — the distance that the stamp will be moved right and up during the $$$i$$$-th operation, respectively.

Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output a single integer representing the perimeter of the colored shape on the paper.

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

Note:
In the first example, the stamp has a side length of $$$3$$$ and is pressed $$$4$$$ times at coordinates $$$(1, 1)$$$, $$$(3, 3)$$$, $$$(5, 4)$$$, and $$$(6, 6)$$$. The piece of paper looks like that afterwards:

Here, the square formed by the first press is colored blue, the second red, the third green, and the fourth purple. The combined shape, whose perimeter we need to calculate, looks like that:

From the diagram, it can be seen that this shape has a perimeter of $$$32$$$.

Example input:
3
4 3
1 1
2 2
2 1
1 2
1 2
1 1
6 7
3 6
1 1
3 1
6 6
5 4
6 1

Example output:
32
8
96

Editorial:
Find the Permutation
Contest: Codeforces Round 997 (Div. 2)
Difficulty rating: 1300
Tags: brute force, dfs and similar, graphs, implementation, sortings

You are given an undirected graph with $$$n$$$ vertices, labeled from $$$1$$$ to $$$n$$$. This graph encodes a hidden permutation$$$^{\text{∗}}$$$ $$$p$$$ of size $$$n$$$. The graph is constructed as follows:

- For every pair of integers $$$1 \le i < j \le n$$$, an undirected edge is added between vertex $$$p_i$$$ and vertex $$$p_j$$$ if and only if $$$p_i < p_j$$$. Note that the edge is not added between vertices $$$i$$$ and $$$j$$$, but between the vertices of their respective elements. Refer to the notes section for better understanding.

Your task is to reconstruct and output the permutation $$$p$$$. It can be proven that permutation $$$p$$$ can be uniquely determined.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains a string of $$$n$$$ characters $$$g_{i, 1}g_{i, 2}\ldots g_{i, n}$$$ ($$$g_{i, j} = \mathtt{0}$$$ or $$$g_{i, j} = \mathtt{1}$$$) — the adjacency matrix. $$$g_{i, j} = \mathtt{1}$$$ if and only if there is an edge between vertex $$$i$$$ and vertex $$$j$$$.

It is guaranteed that there exists a permutation $$$p$$$ which generates the given graph. It is also guaranteed that the graph is undirected and has no self-loops, meaning $$$g_{i, j} = g_{j, i}$$$ and $$$g_{i, i} = \mathtt{0}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case, output $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ representing the reconstructed permutation.

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

Note:
In the first case $$$p = [1]$$$. Since there are no pairs $$$1 \le i < j \le n$$$, there are no edges in the graph.

The graph in the second case is shown below. For example, when we choose $$$i = 3$$$ and $$$j = 4$$$, we add an edge between vertices $$$p_i = 1$$$ and $$$p_j = 3$$$, because $$$p_i < p_j$$$. However, when we choose $$$i = 2$$$ and $$$j = 3$$$, $$$p_i = 2$$$ and $$$p_j = 1$$$, so $$$p_i < p_j$$$ doesn't hold. Therefore, we don't add an edge between $$$2$$$ and $$$1$$$.

In the third case, there are no edges in the graph, so there are no pairs of integers $$$1 \le i < j \le n$$$ such that $$$p_i < p_j$$$. Therefore, $$$p = [6, 5, 4, 3, 2, 1]$$$.

Example input:
3
1
0
5
00101
00101
11001
00001
11110
6
000000
000000
000000
000000
000000
000000

Example output:
1 
4 2 1 3 5 
6 5 4 3 2 1

Editorial:
Palindromic Subsequences
Contest: Codeforces Round 997 (Div. 2)
Difficulty rating: 1200
Tags: brute force, constructive algorithms, math

For an integer sequence $$$a = [a_1, a_2, \ldots, a_n]$$$, we define $$$f(a)$$$ as the length of the longest subsequence$$$^{\text{∗}}$$$ of $$$a$$$ that is a palindrome$$$^{\text{†}}$$$.

Let $$$g(a)$$$ represent the number of subsequences of length $$$f(a)$$$ that are palindromes. In other words, $$$g(a)$$$ counts the number of palindromic subsequences in $$$a$$$ that have the maximum length.

Given an integer $$$n$$$, your task is to find any sequence $$$a$$$ of $$$n$$$ integers that satisfies the following conditions:

- $$$1 \le a_i \le n$$$ for all $$$1 \le i \le n$$$.
- $$$g(a) > n$$$

It can be proven that such a sequence always exists under the given constraints.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$\color{red}{6} \le n \le 100$$$) — the length of the sequence.

Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, representing an array that satisfies the conditions.

If there are multiple solutions, you may output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, one possible solution is $$$a = [1, 1, 2, 3, 1, 2]$$$. In this case, $$$f(a) = 3$$$ as the longest palindromic subsequence has length $$$3$$$. There are $$$7$$$ ways to choose a subsequence of length $$$3$$$ that is a palindrome, as shown below:

1. $$$[a_1, a_2, a_5] = [1, 1, 1]$$$
2. $$$[a_1, a_3, a_5] = [1, 2, 1]$$$
3. $$$[a_1, a_4, a_5] = [1, 3, 1]$$$
4. $$$[a_2, a_3, a_5] = [1, 2, 1]$$$
5. $$$[a_2, a_4, a_5] = [1, 3, 1]$$$
6. $$$[a_3, a_4, a_6] = [2, 3, 2]$$$
7. $$$[a_3, a_5, a_6] = [2, 1, 2]$$$

Therefore, $$$g(a) = 7$$$, which is greater than $$$n = 6$$$. Hence, $$$a = [1, 1, 2, 3, 1, 2]$$$ is a valid solution.

In the second example, one possible solution is $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$. In this case, $$$f(a) = 5$$$. There are $$$24$$$ ways to choose a subsequence of length $$$5$$$ that is a palindrome. Some examples are $$$[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$$$ and $$$[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$$$. Therefore, $$$g(a) = 24$$$, which is greater than $$$n = 9$$$. Hence, $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$ is a valid solution.

In the third example, $$$f(a) = 7$$$ and $$$g(a) = 190$$$, which is greater than $$$n = 15$$$.

Example input:
3
6
9
15

Example output:
1 1 2 3 1 2
7 3 3 7 5 3 7 7 3
15 8 8 8 15 5 8 1 15 5 8 15 15 15 8

Editorial:
Unique Median
Contest: Codeforces Round 997 (Div. 2)
Difficulty rating: 2200
Tags: binary search, brute force, combinatorics, data structures, divide and conquer, dp

An array $$$b$$$ of $$$m$$$ integers is called good if, when it is sorted, $$$b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}$$$. In other words, $$$b$$$ is good if both of its medians are equal. In particular, $$$\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil$$$ when $$$m$$$ is odd, so $$$b$$$ is guaranteed to be good if it has an odd length.

You are given an array $$$a$$$ of $$$n$$$ integers. Calculate the number of good subarrays$$$^{\text{∗}}$$$ in $$$a$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le \color{red}{\textbf{10}}$$$) — the given array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output a single integer representing the number of good subarrays in $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first case, every subarray is good since all its elements are equal to $$$1$$$.

In the second case, an example of a good subarray is $$$b = [10, 2, 3, 3]$$$. When it is sorted, $$$b = [2, 3, 3, 10]$$$, so $$$b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$$$. Another example would be $$$b = [1, 10, 2]$$$. On the other hand, $$$b = [1, 10]$$$ is not good as its two medians are $$$1$$$ and $$$10$$$, which are not equal.

Example input:
3
4
1 1 1 1
5
1 10 2 3 3
10
6 3 2 3 5 3 4 2 3 5

Example output:
10
11
42

Editorial: