| 2026-2027 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
Lobachevsky finds himself on a train whose $$$n$$$ carriages form a cycle. A fire escape plan hangs in every carriage. Each plan shows the entire train, but its "You are here" marker is missing. Lobachevsky wants to add the missing marker, but first he must find out which carriage he is in. He finds the train's geometry a bit confusing, though.
On the plan, the carriages are numbered from $$$1$$$ to $$$n$$$ in clockwise order, and carriage $$$i$$$ has type $$$a_i$$$. Several carriages may have the same type. Lobachevsky knows the entire plan, but not which carriage he starts in. He can observe only the type of the carriage he is currently in.
Each carriage has two connecting doors, one to each neighbor. Lobachevsky can move through either door and knows which one leads clockwise and which one leads counterclockwise. These directions match those on the plan. Passing through one door counts as one move. He observes the type of his starting carriage before making any moves, and the type of his current carriage after each move. He remembers all his moves and observations, and can use them to choose his next move or decide when to stop.
Given the train plan, find the smallest non-negative integer $$$m$$$ such that Lobachevsky has a strategy to determine exactly which carriage he is in after at most $$$m$$$ moves. The strategy must guarantee this for every possible starting carriage. If no such strategy exists, report that instead.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 300$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$, denoting the number of carriages ($$$3 \le n \le 1000$$$).
The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$, denoting the carriage types in clockwise order ($$$1 \le a_i \le n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
For each test case, print $$$m$$$, the minimum number of moves required to guarantee that Lobachevsky can determine his location. If no strategy guarantees success, print $$$-1$$$ instead.
431 2 341 1 2 2121 2 2 1 3 3 1 3 3 1 2 232 2 2
013-1
In the first test case, all carriage types are distinct, so no moves are needed.
In the second test case, Lobachevsky can determine his location after one clockwise move.
In the third test case, if the initial carriage type is $$$2$$$ or $$$3$$$, Lobachevsky can move clockwise three times. If it is $$$1$$$, he can move once counterclockwise and then twice clockwise. In either case, after $$$3$$$ moves he can determine exactly which carriage he ends up in.
| Название |
|---|


