It suffices to brute force all possible arrays, where we can check if the array violates at most ~1~ requirement in ~\mathcal{O}(N^2)~ time.

~\mathcal{O}(N^{N+2})~

We observe that the constructed array must always be non-decreasing. To see this, suppose this wasn't the case and so there exists two indices ~i,j~ such that ~x_i > x_j~. This implies that ~b_i, c_j > 0~. However since ~b_i = c_j = 0~, this would require at least ~2~ modifications which is not allowed.

We also observe that since at most one modification can be made, the constructed array must either satisfy all ~a_i~ or satisfy all ~d_i~. Hence, we can build ~2~ possible arrays, where the first one satisfies all ~a_i~ and the second one satisfies all ~d_i~. For the former, we construct the array from left to right. At each index ~i~, there are two possibilities:

• Case 1: ~a_i = a_{i-1}~
  This means the current element must be equal to the previous element.
• Case 2: ~a_i \ne a_{i-1}~
  Observe that for a solution to exist, ~a_i~ must equal ~i-1~, since the preceeding elements must be less than ~x_i~. We set the value of ~x_i~ to be the next smallest value.

After constructing the first array, we then have to check if it violates at most one ~d_i~

We build the second array using all ~d_i~ in a similar manner. If both arrays can be built, we pick the lexicographically smaller one.

~\mathcal{O}(N)~

We can extend the solution in subtask 2 by recognizing that ~a_i+b_i~ and ~c_i+d_i~ gives the rank of the ~i^{\text{th}}~ element in ascending and descending order respectively. Using ~a_i+b_i~ as an example, notice if we process elements in increasing order of ~a_i+b_i~, we see that the values in the constructed array are uniquely determined based on whether or not the current and previous value of ~a_i+b_i~ are equal.

Once both arrays are constructed, we can check if they satisfy all the requirements in ~\mathcal{O}(N^2)~ time.

For full marks, we can optimize checking if an array satisfies all requirements by using a BIT.

~\mathcal{O}(N\log N)~