Finding farthest item in an array with duplicates
Here's a scheme that does $O(L \lg L)$ preprocessing, and thereafter lets you answer query for the value $x$ in $O(rN \lg L)$ time, where $r$ counts the number of times that $x$ is repeated.  This will be slightly more efficient than the naive algorithm for values $x$ that don't occur too many times in the array, but inefficient for common values.

Here's how.  During preprocessing, we're going to build a map $f$ defined by

$$f(y,i) = \min \{ j&gt;i : A[j]=y \}.$$

Similarly, we're going to build a map $g$ defined by

$$g(y,i) = \min \{j&lt;i : A[j]=y \}.$$

(We'll also build a set of inverted indices that, given $x$, enables us to enumerate all indices where $x$ appears in $A$.)

Note that these maps $f,g$ help us compute the distance function $d$ efficiently.  In particular,

$$d(x,y) = \min \{ f(y,i)-i : A[i]=x \} \cup \{ i-g(y,i) : A[i]=x \},$$

which can be computed with $r$ evaluations of $f$ and $r$ evaluations of $g$.  Consequently, given $x$, we'll be able to find the value $y$ that maximizes $d(x,y)$ using $rN$ evaluations of $f,g$, by simply trying all possibilities for $y$.

We're going to use the preprocessing to arrange things so we can evaluate $f,g$ at an input of our choice in $O(\lg L)$ time.  How do we do that?

Unfortunately, storing $f$ explicitly would take $NL$ space, which is too much.  Fortunately, there is a lot of redundancy in $f$: there are long ranges of indices $i,i+1,\dots,i'$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')$.  This is going to help us represent $f$ more compactly.  Similarly for $g$.

In particular, we'll store $f(y,\cdot)$ as an interval tree: whenever we have an interval $[i,i']$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')=\alpha$, then we add a single interval to the tree with the mapping $[i,i'] \to \alpha$.  In this way, $f$ is stored as $N$ different interval trees.  It is possible to show that the total number of leaves, across all of these interval trees, is at most $L+N=O(L)$ (in particular, the tree for $f(y,\cdot)$ has at most $r'+1$ leaves, where $r'$ counts the number of occurrences of $y$ in $A$).  If we store these trees as balanced binary trees, their height will be upper-bounded by $O(\lg L)$.  Consequently, the total amount of space needed to store these trees is $O(L \lg L)$.  You can also show how to generate these trees in $O(L \lg L)$ time.  Finally, evaluating $f$ at a point of your choice amounts to a stabbing query in the corresponding interval tree, which takes $O(\lg L)$ time.  This shows how to achieve the time complexity quoted in the first sentence of my answer.



As an optimization, if $x$ appears in $A$ more than $L/(N \lg L)$ times, you can answer the query in $O(L)$ time using a standard linear scan (skipping the above cleverness).  Of course, you can detect quickly which values of $x$ occur that often by using the inverted indices built during preprocessing.

With this idea, we get a scheme that requires $O(L \lg L)$ preprocessing and lets us answer each subsequent query in $O(\min(L, rN \lg L))$ time, where $r$ counts the number of times that the queried value occurs in $A$.