Let an array of size n , 1 \leq n \leq 30 is made by permuting the set \{1,2,3 \cdots n\}.

Now I have given some k numbers from the above set , k \leq n numbers which are prefix of the permutation array and now the array is formed by

a_1, a _2, \cdots a_k fixed prefix and remaining permutation of n - k elements a_{k+1}, a_{k+2} \cdots a_n.

Let the sum s is defined by \sum_{i = 1}^n max(0, i - a_i).

How to find all possible values of sum.

Since the first k values are given fixed then \sum_{i = 1}^k max(0, i - a_i) can be found easily but how to find all possible values of \sum_{i = k+1}^n max(0, i - a_i).

For example n = 5 , k = 2

prefix arr = 2 \> 1

\sum_{i = 1}^2 max(0, i - a_i) = max(0, 1 -2) + max (0, 2 - 1) = 0 + 1 = 1

There are 3! = 6 array possible for above prefix.

2 \>1 \>3 \> 4 \>5

Sum = 1 + max(0, 3 - 3) + max(0, 4 - 4) + max(0, 5 - 5) = 0 + 1 + 0 + 0 + 0 = 1

2 \>1 \>4 \> 3 \>5

Sum = 1 + max(0, 3 - 4) + max(0, 4 - 3) + max(0, 5 - 5) = 1 + 0 + 1 + 0 = 2

2 \>1 \>4 \> 5 \>3

Sum = 1 + max(0, 3 - 4) + max(0, 4 - 5) + max(0, 5 - 3) = 1 + 0 + 0 + 2 = 2

2 \>1 \>3 \> 5 \>4

Sum = 1+ max(0, 3 - 3) + max(0, 4 - 5) + max(0, 5 - 4) = 1 + 0 + 0 + 1 = 2

2 \>1 \>5 \> 3 \>4

Sum = 1 + max(0, 3 - 5) + max(0, 4 - 3) + max(0, 5 - 4) = 1 + 0 + 1 + 1 = 3

2 \>1 \>5 \> 4 \>3

Sum = 1 + max(0, 3 - 5) + max(0, 4 - 4) + max(0, 5 - 3) = 1 + 0 + 0 + 2 = 3

so all possible sum = \{ 1, 2 , 3 \}

Finding all permutation of the array is not possible because of very high time complexity. Please help.