¿Se puede verificar la clasificación de una lista sin comparar vecinos?

Una lista de $n$ elementos se puede verificar ordenada comparando cada elemento con su vecino. En mi aplicación, no podré comparar cada elemento con su vecino: en cambio, las comparaciones a veces serán entre elementos distantes. Dado que la lista contiene más de tres elementos y también que la comparación es la única operación admitida, ¿existe alguna vez una "red" de comparaciones que demuestre que la lista está ordenada, pero le falta al menos un vecino a vecino directo? ¿comparación?

Formalmente, para una secuencia de elementos , tengo un conjunto de pares de índices para los cuales sé si , o . Existe un par que falta en el conjunto de comparaciones. ¿Es posible, entonces, demostrar que la secuencia está ordenada?$e_i$$(j,k)$$e_j > e_k$$e_j = e_k$$e_j < e_k$$(l,l+1)$

$(i,i+1)$