hackercupai/hackercup huggingface dataset:
Note that over time, a pair of dots that are next to each other will always stay next to each other.

If \(N\) is even and \(A_i = B_i\) for any \(i\), we know that an answer is not possible by definition. If \(N\) is odd, then there can be at most \(1\) place where \(A_i = B_i\) (the midpoint of the metalike-logo), so we can find it and get the answer in \(\mathcal{O}(N)\), or return \(-1\) if there's more than one \(i\) where \(A_i = B_i\).

Otherwise, every \(A_i \ne B_i\), and we can first just think about each \(i\) as the lower vs higher dot. For a meta-like logo, the relationship always look like this:
```
(even N) (odd N)
3 2 3 5 6 4 -> LLLHHH 3 2 3 x 5 6 4 -> LLLxHHH
4 6 5 3 2 3 -> HHHLLL 4 6 5 x 3 2 3 -> HHHxLLL
```
Let's first consider even \(N\) by simulating the first pattern in reverse:
```
(t) (t-1) (t-2) (t-N/2) (t-N)
LLLHHH LLLLHH LLLLLH LLLLLL HLLLLL HHLLLL HHHLLL
HHHLLL HHHHLL HHHHHL HHHHHH LHHHHH LLHHHH LLLHHH

(t-N-1) (t-2N)
HHHHLL HHHHHL HHHHHH LHHHHH LHHHHH LLHHHH LLLHHH
LLLLHH LLLLLH LLLLLL HLLLLL HLLLLL HHLLLL HHHLLL
```
Thus the pattern repeats after \(2N\) steps. If an answer exists, then at any given time:
* for even \(N\), there's at most \(1\) place when \(A_i < B_i\) inverts to \(A_{i+1} > B_{i+1}\) (or the reverse).
* for odd \(N\), the middle element eithers conform to its left or right side, so this still holds.

Therefore, the midpoint of the metalike logo either be this inversion point, or the first/last element. Either way, there are \(\mathcal{O}(1)\) possible candidates for the midpoints. After we've found these candidates, we can simulate \(2N\) steps on the input arrays using a double-ended queue (updating the positions of the midpoint candidates at each step). If at any time a midpoint candidate actually shifts to the midpoint, we can do a check to see if \(A\) equals the reverse of \(B\).

There are \(\mathcal{O}(1)\) midpoint candidates, and each can only reach the midpoint twice in our \(2N\) simulated time steps. Thus, the reverse condition is checked at most \(\mathcal{O}(1)\) times. The overall running time is \(\mathcal{O}(N)\).