## Problem Overview

• Consider the permutation 1 to $$n$$ called $$P$$.
• The parameters $$l, r, s$$ that satisfies $$1 \leq l \leq r \leq n$$ and $$1 \leq s \leq \frac{n(n + 1)}{2}$$ are given.
• Find the permutation which satisfies $$P_{l} + P_{l + 1} + … + P_{r} = s$$.
• Print any permutation of length $$n$$ that fits the condition above if such a permutation exists; otherwise, -1.

## Problem Explanation

First, consider the minimum and the maximum value we can generate with the length $$r - l + 1$$.
Hereafter, we define $$k = r - l + 1$$.

Minimum Value
As an arithmetic sequence with first term 1, term number $$m$$, and tolerance 1, we can derive the minimum value.
$$min(m) = \frac{m(m + 1)}{2}$$

Maximum Value
As an arithmetic sequence with first term $$x$$, term number $$m$$, and tolerance -1, we can derive the maximum value.

$$max(x, m) = \frac{m * (2 * x + (m - 1) * -1)}{2}$$
$$max(x, m) = \frac{m(2x - m + 1)}{2}$$

Any number $$s$$ that satisfies $$min(k) \leq s \leq max(n, k)$$ meet the condition.

Coding
First, we prepare the vector $$res$$ with size $$n$$ to push the results.
Consider in descending order.
Start the for loop from $$n$$,
if $$i$$ meets the condition $$max(i, k) - s \geq 0$$ and $$s - i \geq min(k - 1)$$, put $$i$$ to the $$res[l + k]$$ and replace $$k = k - 1, s = s - i$$.
Iterate this until $$k$$ becomes 0, and then if $$s = 0$$ is achieved, we find the permuation; otherwise, prints -1.
The remaining part of the implementation is to insert the unused numbers into the empty parts of the vector.

Source Code