### xuanji's blog

By xuanji, history, 3 months ago,

Curious if anyone knows how to solve the following problem faster than $O(n^2)$.

Given an array $a$ of length $n$ and an integer $n$, find any two numbers $l$ and $r$ ($l \le r)$ such that:

• Let $a'$ be the subarray $a_l, a_{l+1}, ... a_r$. Then for each $x$ that appears in $a'$, $x$ appears in $a'$ at least $k$ times (i.e. $k$ or more array elements are equal to $x$).
• The value $r-l$ is maximized.

Source of problem: I misread https://codeforces.com/contest/1676/problem/F