### PROBLEM LINK:

**Author:** Erfan alimohammadi

**Tester & Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy

### PREREQUISITES:

None

### PROBLEM:

Chef has N markers. There is a cap on each marker. For each valid i, the i_{th} marker has colour a_i. Initially, for each valid i, the colour of the cap on the i_{th} marker is also a_i.

Chef wants to rearrange the caps in such a way that no marker has the same color as its cap. (Obviously, each marker must have exactly one cap.) Can he do that? If he can, find one such way to rearrange the caps. If there are multiple solutions, you may find anyone.

### EXPLANATION

If thereâ€™s one color such that thereâ€™s more than \lfloor \frac{N}{2} \rfloor pens having this color then itâ€™s impossible to do the task. Because if for each pen we bring one cap from different color, at least one pen of these wonâ€™t have any remaining different cap to match with it.

Letâ€™s sort pens according to their color value (sorting itself is not important) but we need to make sure that all pens that have the same color are consecutive in the sorted list.

Let h=\lfloor \frac{N}{2} \rfloor and letâ€™s assume that the list is 0-indexed.

For the i_{th} pen in the sorted list that has color a_i letâ€™s match it with the ((i+h)\, mod\, N)_{th} pen cap.

Itâ€™s guaranteed that we would have a different color. According to our hypothesis that we canâ€™t have more than h pens having the same color, and since each colorâ€™s pens are consecutive. Definitely, our cap will have a different color. (Think about it a little bit).