Songwriter (Problem E, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Alfonsus Raditya Arsadja

# Problem Statement

Andi is a mathematician, a computer scientist, and a songwriter. After spending so much time writing songs, he finally writes a catchy melody that he thought as his best creation. However, the singer who will sing the song/melody has a unique vocal range, thus, an adjustment may be needed.

A melody is defined as a sequence of $N$ notes which are represented by integers. Let $A$ be the original melody written by Andi. Andi needs to adjust $A$ into a new melody $B$ such that for every $i$ where $1 \leq i < N$:

- If $A_i < A_{i+1}$, then $B_i < B_{i+1}$.
- If $A_i = A_{i+1}$, then $B_i = B_{i+1}$.
- If $A_i > A_{i+1}$, then $B_i > B_{i+1}$.
- $|B_i - B_{i+1}| \leq K$, i.e. the difference between two successive notes is no larger than $K$.

Moreover, the singer also requires that all notes are within her vocal range, i.e. $L \leq B_i \leq R$ for all $1 \leq i \leq N$.

Help Andi to determine whether such $B$ exists, and find the lexicographically smallest $B$ if it exists. A melody $X$ is lexicographically smaller than melody $Y$ if and only if there exists $j$ $(1 \leq j \leq N)$ such that $X_i = Y_i$ for all $i < j$ and $X_j < Y_j$.

For example, consider a melody $A = \{1, 3, 5, 6, 7, 8, 9, 10, 3, 7, 8, 9, 10, 11, 12, 12\}$ as shown in the following figure. The diagonal arrow up in the figure implies that $A_i < A_{i+1}$, the straight right arrow implies that $A_i = A_{i+1}$, and the diagonal arrow down implies that $A_i > A_{i+1}$.

![IMAGE](icpc-jakarta-2019-song-1.png)

Supposed we want to make a new melody with $L = 1$, $R = 8$, and $K = 6$. The new melody $B = \{1, 2, 3, 4, 5, 6, 7, 8, 2, 3, 4, 5, 6, 7, 8, 8\}$ as shown in the figure satisfies all the requirements, and it is the lexicographically smallest possible.


# Input

Input begins with a line containing four integers: $N\ L\ R\ K$ ($1 \leq N \leq 100\ 000$; $1 \leq L \leq R \leq 10^9$; $1 \leq K \leq 10^9$) representing the number of notes in the melody, the vocal range ($L$ and $R$), and the maximum difference between two successive notes in the new melody, respectively. The next line contains $N$ integers: $A_i$ ($1 \leq A_i \leq 10^9$) representing the original melody.

# Output

Output in a line $N$ integers (each separated by a single space) representing the lexicographically smallest melody satisfying all the requirements, or output -1 if there is no melody satisfying all the requirements. Note that it might be possible that the lexicographically smallest melody which satisfies all the requirements to be the same as the original melody.

# Sample Input #1
```
16 1 8 6
1 3 5 6 7 8 9 10 3 7 8 9 10 11 12 12
```
# Sample Output #1
```
1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 8
```
# Explanation for the sample input/output #1

This is the example from the problem description.

# Sample Input #2
```
16 1 8 6
1 3 5 6 7 8 9 10 3 7 8 9 10 11 12 13
```
# Sample Output #2
```
-1
```
# Sample Input #3
```
16 1 10 10
1 3 5 6 7 8 9 10 3 7 8 9 1 11 12 13
```
# Sample Output #3
```
1 2 3 4 5 6 7 8 1 2 3 4 1 2 3 4
```

Sample inputs:
16 1 8 6
1 3 5 6 7 8 9 10 3 7 8 9 10 11 12 12

16 1 8 6
1 3 5 6 7 8 9 10 3 7 8 9 10 11 12 13

16 1 10 10
1 3 5 6 7 8 9 10 3 7 8 9 1 11 12 13

Sample outputs:
1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 8

-1

1 2 3 4 5 6 7 8 1 2 3 4 1 2 3 4

# Solution Analysis
Analysis author: Alfonsus Raditya Arsadja

First of all, we can ignore the original sequence $A$ and just get the relation between every 2 consecutive numbers in $A$. At first glance, it looks like it can be done with a greedy approach from left to right; but if the sequence is almost all decreasing or most of them are decreasing, we have to make an adjustment to the elements prior to the current element when making $B$. It can be seen that the worst case is for every position, we will be updating all numbers below the current position, results in $O(n^2)$. We need something faster.

It can be seen that for every position, the numbers that have solutions formed a range. We define 2 functions, $low$ and $high$, that receives $i$ as an input and returns the lowest and highest number that have a solution for position $i$, respectively; So for every position $i$ ($1 \le i \le N$), every number $x$ in which $low_i \le x \le high_i$, we can find a solution that contains $x$ as a number in position $i$ of the new sequence $B$.

Note: If two consecutive elements have equal value, the values of 2 functions in corresponding indices will be equal too. So for simplicity, we ignore the consecutive elements that have equal value and only consider the rest.

We can generate the values of $low$ and $high$ as the following:

$$
(low_i, high_i) =
\begin{cases}
(L, R), & i = N \\\\
(\max((low_{i+1} - K, L), high_{i+1} - 1), & 1 \le i < N, A_i < A_{i+1} \\\\
((low_{i+1} + 1, \min(high_{i+1} + K, R)), & 1 \le i < N, A_i > A_{i+1}
\end{cases}
$$

If there exists some position $i$ that $low_i > R$ or $high_i < L$, there is no solution. Otherwise, there exists a solution for given constraints and configuration. As we want the lexicographically smallest sequence, we generate $B$ from the smallest position.

The element that fills the first position (position 1) will be $low_1$ itself, as it is the lowest possible number that has a solution. In every following position, we can simulate the similar algorithm with the $low$ and $high$ function above, but this time only considers the previous number that just been generated, and the $low$ and $high$ functions that have been generated before. So if $A_{i-1} < A_i$, $B_i$ must be somewhere inside $[B_{i-1}+1, B_{i-1} + K]$, and vice versa. But $B_i$ must also somewhere inside $[low_i, high_i]$, so we just check the lowest number that falls into both range, and it gives the value of $B_i$. It is guaranteed that there exists a number that falls into both ranges at the same time, as we already checked there is a solution first.

This solution runs in linear time, hence $O(N)$, enough to pass within the time limit.


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}