List of Lists

You’re given:

An integer N and an array A of size N.
Initially you have N lists:

Li=[Ai].

Operation (allowed while at least 2 lists exist):

Pick two non-empty lists Li, Lj with i≠j.
Append Lj to Li (concatenate), then delete Lj from the set of lists.

Goal: Obtain a final set of lists such that:

For every list, first element = last element.
The first element of all lists is the same.
Minimize the number of operations.
If impossible, print -1.

Key Observations

First and last element equal in each list

After all operations, each list must look like:

[x, …, x] (first and last element both x), possibly of length 1.

Same first element across lists

All lists must start with the same value, say X.

So any list whose first element is not X in the final state must be merged into a list starting with X

Length-1 lists already good

Any list [v] already has first = last = v, and if v = X then it already satisfies both conditions without needing merges.

Merging changes the last element of the target list

If we append list Lj to Li:

New first element of Li = old first of Li (unchanged).
New last element of Li = old last of Lj.

To keep the final list’s first and last equal to X, the last list appended to a list with first element X must also end with X.

Strategy

We must pick a value X that will be the common first element of all final lists.

Let’s count how many times each value appears in A:

For value v, let freq[v] be its count.

Candidate X must appear at least once (obvious), but also:

If N = 1, the single list [A1]already works → answer = 0.
If all elements are distinct and N > 1, no way to form a list starting and ending with the same value of length > 1, except singletons. But then different singles would start with different values → impossible.

Core idea from editorial-type reasoning:

If all elements are the same:

Example: [x, x, x, x]
Initially: N lists [x].
Any number of operations keep all lists with first and last = x.
The conditions are already satisfied from the start: multiple lists, all [x].
Minimal operations = 0.

If not all elements are the same, but there is at least one value X that appears at least twice:

We can build at least one list that starts and ends with X by combining two [X] plus possibly other in-between lists:

Example: [X] + ... + [X] → [X, ..., X].

All other elements can be merged (directly or indirectly) into that structure in such an order that the starting element remains X and the final element is also $X`.
The crucial fact: as long as there is some duplicate value, we can always manage to get the required configuration.
In that scenario, we ultimately want to merge all lists into a single valid list satisfying both conditions (this is always at least as good as leaving multiple lists, because we’re minimizing operations and each merge reduces number of lists by 1).

Since we start with N lists, to end with 1 list, we need exactly 1 operations (every merge removes one list).
And we can arrange merges so that the final list starts and ends with some value X that occurs at least twice.

If no element appears twice (all values distinct, max freq = 1) and N > 1:

Any list formed by concatenating distinct singletons will have first and last different.
The only lists that can have equal first and last are singletons, but then they have different starting values → you can’t satisfy “first element of all lists is the same”.=> Impossible → answer = -1.

Final Rule:

For each test case:

Count frequencies of each value in A.
Let maxFreq be the maximum frequency.
If N == 1:

Answer = 0 (trivially satisfies conditions).

Else if maxFreq == 1:

Answer = -1 (no duplicates, impossible).

Else:

It is always possible to form such a structure by merging everything into a single valid list.
Minimum operations = number of merges needed to reach 1 list = N - 1.

So: