[Solution] Range Assign, Number of Distinct Elements Minimize CodeChef Solution

Problem

You are given an array $A$ of $N$ positive integers.

In one operation, you can do the following:

• Choose integers $i$ and $j$ $(1 \le i < j \le N)$, such that $A_i = A_j$;
• For all $k$ $(i < k < j)$, change the value of $A_k$ to $A_i$.

Find out whether $A$ can have at most $2$ distinct values after using any (possibly zero) number of operations.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input:
  • The first line of each test case contains $N$ - the size of the array.
  • The next line contains $N$ integers, $A_1, A_2, A_3, \ldots, A_N$ - the elements of the array.

Output Format

For each test case, print YES if $A$ can have at most $2$ distinct values after using any (possibly zero) number of operations and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

Explanation:

Test case $1$: The array $A$ already has $2$ distinct elements.

Test case $2$: It is impossible to make operations such that $A$ has $2$ distinct elements.

Test case $3$: We can make an operation as:

• Choose $i = 1$ and $j = 3$. Thus, we change $A_2$ to $A_1 = 1$.

The final array is $[1,1,1,3]$ which has two distinct elements.

Test case $4$: We can make an operation as:

• Choose $i = 1$ and $j = 4$. Thus, we change $A_2$ and $A_3$ to $A_1 = 1$.

The final array is $[1,1,1,1]$ which has one distinct element.