### PROBLEM LINK:

**Author:** Chandan Boruah

**Tester:** Pushkar Mishra

**Editorialist:** Florin Chirica

### PROBLEM

Let’s define a ranklist as a sequence of numbers between 1 and x of length n, such as ALL numbers between 1 and x must appear in the sequence at least once. An operation can change one element in what value you want. Your goal is to create a sequence containing all numbers between 1 and n exactly once by using minimal number of operations.

### QUICK EXPLANATION

Let’s iterate a number x meaning that all numbers between 1 and x appear in the ranklist. The cost of *any* ranklist with values between 1 and x is n - x. We need to determine if numbers between 1 and x are enough to create a sum s. Let’s note that a ranklist defined by x can create all sums between minSum and maxSum, where minSum = x * (x + 1) / 2 + (n - x) and maxSum = x * (x + 1) / 2 + (n - x) * x.

### EXPLANATION

To solve this problem, we need to make two observations. They seem pretty easy and intuitive, but after we make them, the problem is solved.

**Observation 1**

A ranklist containing elements between 1 and x (no element greater than x) will need n - x operations to be transformed into a sequence of numbers between 1 and n, no matter how sequence looks like.

We already have all elements between 1 and x (from the definition of a ranklist). However, we need to also have elements x + 1, x + 2, …, n - 1, n. Those do not appear (since all are greater than x), so we have to make some operations to get them. We can keep exactly one position which contains a value i, for each i between 1 and x. Rest of n - x positions must be modified. We’ll put in the remaining n - x positions values x + 1, x + 2, …, n - 1 and n. So cost of a ranklist containing elements between 1 and x becomes n - x.

**Observation 2**

A ranklist containing elements between 1 and x (no element greater than x) can generate all sums s, such as minSum <= s <= maxSum. More, all sums that can be generated by this ranklist are the ones that are between minSum and maxSum.

Let’s find out who is minSum. We are forced to place x elements: 1 2 … x. The rest of them we can complete them with 1s. So minSum = (1 + 2 + … + x) + (n - x) = x * (x + 1) / 2 + (n - x). maxSum can be obtained by completing the first x elements 1 2 … x and the rest of them with x value (the maximum we’re allowed to use). So we get maxSum = (1 + 2 + … + x) + (n - x) * x = x * (x + 1) / 2 + (n - x) * x.

Obviously, no sum s can be less than minSum or greater than maxSum (because those values are the minimum/maximum one can get). Let’s proof now that each sum s which has minSum <= s <= maxSum can be obtained. The idea is to see how those n - x terms can vary: they can be from 1 1 1 … 1 1 1 to x x x … x x x. Suppose we obtained a configuration corresponding to a sum s. Unless s is equal to maxSum, we can always obtain s + 1 as well. If s equal to maxSum, then all terms are equal to x. Otherwise, at least one term isn’t x. Since it isn’t x, we can increment it. Now, the obtained sum is s + 1 and it’s obtained assuming that s is different from maxSum.

**Putting the observations together**

In fact, those 2 observations are enough to solve the problem. The key that puts them together is that we can iterate x from 1 to n. Let’s see for a fixed x if a sum s can be obtained. For the given x, we can calculate minSum and maxSum and if minSum <= x <= maxSum, then sum s can be obtained and a ranklist containing only values between 1 and x is valid. The cost to transform this ranklist into 1 2 … n is n - x. So, for all valid ranklists (those who can give sum s), we keep minimum of n - x and we’re done.

**Time Complexity**

Since we iterate the x variable from 1 to n, the complexity is O(n).