Suppose you have a *sorted* vector {xi}i=1n whose elements are all positive and contain no tie (=no two elements in this vector are the same).

I'm looking for the smartest way to check that:

2xi - xj - xk != 0 for all 1 <= i != j != k <= n.

I have a hunch that this could be done in time O(nlog n), or otherwise in better than naive time, perhaps using a strategy similar to what is developed in the answers to [this question](https://stackoverflow.com/questions/25866339/c-check-if-any-of-the-previous-5-or-next-5-elements-equal-a-value).

Recall that the entries of x are all positive and sorted so the entries of x\_k+k\_j are sorted as well.

P.S. Im looking for algorithmic/language agnostic ideas. The c++ tag is mainly there
in case doing this requires taking advantage of some smart caching strategy.

Edit:
=====

@liori makes a good point below, that finding the pair (j,k) for a given i is O(n), using an algorithm similar to what is done [in the last iteration of this answer to a related question](https://codereview.stackexchange.com/questions/38994/finding-pair-of-sum-in-sorted-array/38996#38996). The issue here is IMO whether it is possible to combine these many O(n) steps more efficiently than naively. For example, we can find the pair (j,k) for a given index i in time O(n). But do we need to consider again *all* the the entries j'<=j
and k'<=k as candidates for the following index i'=i+1? Does these savings somehow add up?