ABAB

First, coordinate-compress the values. Only equality between values matters, so this does not change the answer.

For every value $x$, maintain:

• $\operatorname{last}[x]$: the last position where $x$ occurs in the whole sequence;
• $\operatorname{recent}[x]$: the most recent occurrence of $x$ before the current position.

Suppose position $k$ is being processed and $x=A_k$. Let $i=\operatorname{recent}[x]$. The answer is YES if there is a value $y$ such that

$$i<\operatorname{recent}[y]<k<\operatorname{last}[y].$$

Indeed, setting $j=\operatorname{recent}[y]$ and $l=\operatorname{last}[y]$ gives the required four positions. The strict inequality $\operatorname{recent}[y]>\operatorname{recent}[x]$ also guarantees $x\neq y$.

Thus, among values that occur again after the current position, we need the largest recent occurrence position.

Whenever value $x$ occurs at position $t$ and $\operatorname{last}[x]>t$, append $(t,x)$ to a stack. The appended positions are strictly increasing, so the valid pair with the largest position is always at the back of the stack.

Before processing position $k$, repeatedly remove the last pair $(t,y)$ if either:

• $\operatorname{recent}[y]\neq t$, meaning a newer occurrence of $y$ has made the pair stale; or
• $\operatorname{last}[y]\leq k$, meaning $y$ does not occur after position $k$.

After these removals, the last pair stores the largest recent occurrence among all values that occur again later. Therefore, if $x$ has appeared before and the last stored position is greater than $\operatorname{recent}[x]$, the answer is YES.

To prove completeness, suppose

$$i<j<k<l,\qquad A_i=A_k=x,\qquad A_j=A_l=y$$

is a valid answer. Let $k'$ be the first occurrence of $x$ after $j$, and let $i'$ be the previous occurrence of $x$. Then

$$i'\leq i<j<k'\leq k<l.$$

When processing $k'$, the recent occurrence of $y$ is at least $j$, and its last occurrence is at least $l$. Hence a valid pair with position greater than $i'$ exists in the stack, so the algorithm detects the pattern.

Each pair is pushed and popped at most once. The scan after coordinate compression takes $O(N)$ time. The total time complexity is $O(N\log N)$ and the memory complexity is $O(N)$.

Solution written by GPT5.6