In an array of 2N elements that is both 2-ordered and 3-ordered, what is the…

Concept: An array A is called h-ordered (also h-sorted) when A[i] ≤ A[i+h] for every index i at which both entries exist — that is, every subsequence taken with stride h is already in non-decreasing order. Being 1-ordered is therefore exactly the same as being fully sorted. Note that this is a condition on PAIRS of entries; it does not by itself say how far any single entry has drifted.

Concept (chaining): If an array is both p-ordered and q-ordered, the two inequalities chain together: A[i] ≤ A[i+p] ≤ A[i+p+q] ≤ … . So the array is automatically d-ordered for every distance d that can be written as d = a·p + b·q with non-negative integers a and b.

Application:

1. Here p = 2 and q = 3. Every integer d ≥ 2 is a non-negative combination of 2 and 3: 2 = 2, 3 = 3, 4 = 2 + 2, 5 = 2 + 3, 6 = 3 + 3, and any larger d is (d − 2) + 2.

2. Chaining the two given conditions therefore yields A[i] ≤ A[i+d] for every d ≥ 2 and every valid index i.

3. So no two entries lying 2 or more positions apart can be out of order. The only pairs still free to be inverted are adjacent pairs, at distance exactly 1.

4. If some entry had to travel 2 or more positions to reach its place in the sorted array, it would have to be inverted with respect to an entry at distance 2 or more — which step 3 forbids. Hence every entry lies within 1 position of its sorted index.

Cross-check:

• The bound is attained, not merely an upper limit: in [2, 1, 3, 4, 5, …, 2N] every distance-2 pair increases (2 < 3, 1 < 4, 3 < 5, …) and every distance-3 pair increases (2 < 4, 1 < 5, …), so the array is both 2-ordered and 3-ordered — yet the entries 2 and 1 each sit exactly 1 position away from their sorted index.

• Both conditions are genuinely needed. The array [1, 4, 2, 5, 3, 6] is 2-ordered (1 < 2, 4 < 5, 2 < 3, 5 < 6) but not 3-ordered (4 > 3). In it the entry 4 sits 2 positions from its sorted index, so 2-ordering on its own does not pin the drift to 1 position; it is the two conditions together that close off every distance of 2 or more.

Maximum distance from the 1-ordered position = 1.