Distinct Subarray Sum Avoidance

Given a permutation \(p = (p_1, p_2, \ldots, p_n)\) of the integers \(1,2,\ldots,n\), construct a sequence \(a = (a_1, a_2, \ldots, a_n)\) of positive integers such that:

• For every \(i\), \(1 \le a_i \le n\).
• There does not exist any pair of indices \((l, r)\) with \(1 \le l \le r \le n\) satisfying \[ \sum_{i=l}^{r} a_i = \sum_{i=l}^{r} p_i. \]

If such a sequence cannot be constructed, report No solution.

Note: The time limit for this problem is strict.

Explanation: For \(l=r\) the condition forces \(a_i\neq p_i\) for every \(i\). In general, if we define the prefix sums of \(a\) and \(p\) as \[ A_i = \sum_{j=1}^{i} a_j, \quad P_i = \sum_{j=1}^{i} p_j, \quad A_0 = P_0 = 0, \] then the condition is equivalent to requiring that for every \(0 \le i < j \le n\) we have \[ A_j - P_j \neq A_i - P_i. \quad (\star) \] A common way to satisfy \((\star)\) is to choose a sequence of offsets \(d_i = a_i - p_i\) so that the cumulative sums \[ S_i = \sum_{j=1}^{i} d_j\] are all distinct (with \(S_0=0\)), while making sure that the choice of \(d_i\) keeps \(a_i = p_i+d_i\) within \([1,n]\). Note that for each \(i\) the value \(d_i\) is forced to lie in the interval \[ 1-p_i \le d_i \le n-p_i\] and \(d_i\) cannot be zero (since that would yield \(a_i=p_i\) and a violation for \(l=r\)). A solution (if one exists) can be found via a backtracking search over the allowed choices for \(d_i\).

inputFormat

The first line contains a single integer \(n\) (the length of the permutation). The second line contains \(n\) space‐separated integers \(p_1, p_2, \ldots, p_n\), which form a permutation of \(1,2,\ldots,n\).

outputFormat

If a required sequence \(a\) exists, output \(n\) integers \(a_1, a_2, \ldots, a_n\) separated by spaces. Otherwise, output a single line containing No solution (without quotes).

sample

3
1 2 3

No solution