### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

For both of the editorials below the credit goes solely to Anton Lunyov. These are pasted from his mail of solution explanations.

**O(N * N * logN) approach:**

Let’s fix **i1** and **i3**, such that **A[i[1]]** and **A[i[3]]** are in the same relation as **B1** and **B3**, and try to check whether there exists a subsequence **(i[0]**, **i1, i2, i3, i4)** that satisfies conditions of the problem.

Clearly segments on which lie **i[0]**, **i2** and **i4** are disjoint. Denote the segment for **i[j]** by **[x[j], y[j]]**.

Let **B[R]** be the maximum in the set **S={ B[0], B2, B4 }, B[L]** be the minimum in **S**, and **B[M]** be the middle element.

Values **A[i[1]]** and **A[i[3]]** dictate some segments on which should lie values **A[i[0]], A[i[2]]** and **A[i[4]]**. Segment **[X[j], Y[j]]** for **A[i[j]]** depends on relation between **B1, B3** and **B[j]** and can be found easily.

After we find these segments it is clear that it is advantageous to take for **i[L]** such value on the segment **[x[L], y[L]]** that **A[i[L]]** is minimal possible under condition **A[i[L]]>=X[L]**. The similar is true for **i[R]** but we should maximize **A[i[R]]** under condition **A[i[R]]>=X[R]**.

After **i[L]** and **i[R**] is chosen they dictate some changes to the segment for **A[i[M]]**. In some cases this segment becomes empty and it means that required subsequence does not exist in this case. Otherwise we should check whether there exists some **i[M]** in **[x[M]**, **y[M]]** such that **A[i[M]]** in **[X[M], Y[M]]**, where **[X[M], Y[M]]** can be modified after choosing **i[L]** and **i[R]**.

To answer the question for the fixed pair **(i1**, **i3)** quickly we at first change array **A[]** by the new one where all relations between elements are saved but values are between **1** and **N** and then compute values **S[j][V]** - the total amount of numbers not greater than **V** among the numbers **A1**, …, **A[j]**. This can be done by simple dynamic programming in **O(N*N)** time.

With this array we can answer in **O(1)** time on the following question: for how many **j** in **[x, y]** we have **A[j]** in **[X, Y]**. With this ability we can find values **A[i[L]]** and **A[i[R]]** by binary search in **O(log N)** time (but not the values of **i[L]** and **i[R]** itself) and then in **O(1)** time check whether there exist appropriate i[M].

Once we find that for the given pair **(i1, i3)** the required subsequence do exist, we can restore the answer in **O(N)** time knowing values **A[i[L]],A[i[R]]** and segment for **A[i[M]]**, print it and stop further checks. Using some additional **O(1)** checks before applying binary search we can decrease the total number of pairs for which we should use binary search in some cases.

**O(N*N) approach:**

Take the notations of the previous solution. Let’s precompute the following values:

pref_min[j][V] = min(A[i] : 1<=i<=j, A[i]>=V).

pref_max[j][V] = max(A[i] : 1<=i<=j, A[i]<=V).

suff_min[j][V] = min(A[i] : j<=i<=n, A[i]>=V).

suff_max[j][V] = max(A[i] : j<=i<=n, A[i]<=V).

Each of this tables can be precomputed in O(N*N) time.

Consider for example pref_min[][]:

pref_min[j][V]=min(pref_min[j-1][V], A[j]>=V?A[j]:inf);

Now how can we use this information?

Let i1 and **i[3**] be fixed

Consider indexes **L** and **R**.

(Just for clarity: Let **B[R]** be the maximum in the set **S={ B[0], B2, B4}, B[L]** be the minimum in **S**, and **B[M]** be the middle element.)

At least for one of them, say **L**, corresponding segment **[x[L], y[L]]** for **i[L]** has the form **[1,i1-1]** or **[i[3]+1,n]**.

Hence we can choose **A[i[L]]** in the way we want (for clarity: it is advantageous to take for **i[L]** such value on the segment **[x[L], y[L]]** that **A[i[L]]** is minimal possible under condition **A[i[L]]>=X[L])** just looking at value pref_min[i[1]-1][X[L]] or suff_min[i[3]+1][X[L]].

WLOG assume that [x[L], y[L]] = [i[3]+1, n].

Now consider those of indexes M and R for which corresponding segment is **[1, i1-1]**.

If this index is **R** then **A[i[R]]=pref_max[i[1]-1][Y[R]]**.

If this index is **M** then **A[i[M]]=pref_min[i[1]-1][X[M]**] since after minimizing **A[i[L]]** it is advantageous to minimize **A[i[M]]** in its segment (but note that X[M] may change after computing of **A[i[L]]**)

Finally for last value among **R** and **M** that left we need to look at our table **S[][]** to see whether there exist such value that

**i1<i[K]<i3 and X[K] <= A[i[K]] <= Y[K]** where **K** is **M** or **R**.

Unfortunately my implementation of this **O(N*N)** approach performs much slower than Anton Lunyov’s code of **O(N * N * logN)** for any of the test cases we could make.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.