Binary Not Search and Queries

Core Observation

Let $W_p(k)$ be the multiset of the length-$k$ window starting at $p$.

First look at adjacent windows:

$W_p(k)$ and $W_{p+1}(k)$ differ only by removing $a_p$ and adding $a_{p+k}$. Therefore

$W_p(k)=W_{p+1}(k)$ iff $a_p=a_{p+k}$.

That means every pair of equal values at positions $l<r$ immediately gives a valid tuple with $k=r-l$: compare $[l,r-1]$ and $[l+1,r]$. So the answer's length is at least the largest distance between two equal values.

Now prove it cannot be bigger. Suppose two length-$k$ windows starting at $i<j$ have the same multiset. If $j-i>k$, then $a_i$ must appear inside the second window, more than $k$ positions to the right. Otherwise, cancel the overlap of the two windows. The remaining left piece is $[i,j-1]$, and the remaining right piece is $[i+k,j+k-1]$; these two pieces have the same multiset. The element $a_i$ must appear in the right piece, at position at least $i+k$.

Either way, a valid length $k$ forces some equal pair of values at distance at least $k$. So:

$k_{\max}=\max_v(\text{last occurrence of }v-\text{first occurrence of }v)$.

If no value appears twice, the set $S(a)$ is empty and the answer is $0,0$. No drama, just dead.

Counting Optimal Tuples

Let $K=k_{\max}$.

A position $p$ is called good if $a_p=a_{p+K}$. Then the length-$K$ windows starting at $p$ and $p+1$ are equal.

Because $K$ is the maximum possible equal-value distance, if $a_p=a_{p+K}$, then $p$ must be the first occurrence of that value and $p+K$ must be its last occurrence. So good starts are exactly:

$\text{first}_v$ for all values $v$ with $\text{last}_v-\text{first}_v=K$.

Now comes the sneaky bit. For maximum length $K$, if two windows $W_i(K)$ and $W_j(K)$ are equal, then all adjacent steps between them must also be equal:

$W_i(K)=W_{i+1}(K)=\cdots=W_j(K)$.

Why? If $j-i>K$, then the first element would need an equal copy farther than $K$, impossible. Otherwise, after canceling overlap, match the left leftover positions to the right leftover positions. The first leftover position $i$ can only match $i+K$, because matching anything farther would create an equal-value distance greater than $K$. Remove that pair and repeat. Induction forces $a_p=a_{p+K}$ for every $p$ from $i$ to $j-1$.

So an optimal tuple $(i,j,K)$ is exactly a nonempty consecutive block of good starts: $i,i+1,\ldots,j-1$.

If a maximal run of good starts has length $r$, it contributes

$r+(r-1)+\cdots+1 = r(r+1)/2$

valid tuples. Therefore $f(a)$ is the sum of $r(r+1)/2$ over all consecutive runs of good starts for length $K$.

Dynamic Maintenance

For every value $v$, keep an ordered set of its positions.

If $v$ appears at least twice, it contributes:

• span $d_v=\text{last}_v-\text{first}_v$ to a global multiset of spans;
• one candidate start at position $\text{first}_v$ inside the bucket for length $d_v$.

The global multiset tells us the current $K$ from its largest element.

For each possible length $d$, maintain these candidate starts grouped into maximal consecutive intervals. Also maintain ways[d], the sum of $r(r+1)/2$ over those intervals.

Tiny but important caveat: for non-maximum $d$, this bucket is not necessarily the real answer for length $d$. That is fine. We only ever read the bucket for the current maximum span $K$, and for that length the candidates are exactly the good starts. Trying to maintain every length perfectly would be self-inflicted pain. Classic Codeforces tax, avoided.

When inserting a start position $p$ into bucket $d$:

• create interval $[p,p]$;
• merge with the interval ending at $p-1$, if it exists;
• merge with the interval starting at $p+1$, if it exists;
• update ways[d] by removing old interval contributions and adding the merged one.

Deletion is the reverse: remove the interval containing $p$, then split into up to two intervals.

A point update $a_i=x$ affects only two values: the old value and $x$. Remove their old contributions, change the position sets, then insert their new contributions.

Finally:

• if the span multiset is empty, print 0 0;
• otherwise $K$ is its maximum element, and the answer is K ways[K].

Each update does a constant number of ordered-set operations, so the total complexity is $O((n+q)\log n)`.