More and more Olympiads are being held on the codeforces platform. I would like to be able to add a column to the standings, which will display, for example, whether a participant has passed to the next stage or his final place (like medals at the finals).

Example

You are given an array $$$a$$$ of length $$$n$$$. Notice that array can contain dupilcate elements.

You can perform the following operation:

• choose two integers $$$i$$$, $$$j$$$ such that $$$1\leq i,j \leq n$$$
• swap $$$a_i$$$ and $$$a_j$$$

Find the minimum number of operations to sort the array.

It seems like a very natural problem, but I didn't find any solutions to it. Does anyone know the solution?

Some thoughts:

Let $$$a'$$$ be an array $$$a$$$ after sorting. Let's consider a graph $$$G$$$ with edges $$$a'[i] \rightarrow a[i]$$$. So now we need to somehow decompose this graph into cycles, such that the number of cycles is maximum.

To do that we can notice that $$$G$$$ is an euliran graph so we can find an euler cycle of it (let's store it in array $$$p$$$). Now each cycle in $$$G$$$ is some segment in $$$p$$$ which starts and ends in the same number (actually it can be circural segment). So we have some segments in $$$p$$$ and we need to find the maximum number of segments, such that they do not intersect (but they can lie inside each other and touch). This problem seems like some dp on segments, but I didn't figure it out yet.

Recently I've come up with this problem:

You are given an array $$$a_1, a_2, \dots, a_n$$$ of positive integers.

You need to find $$$l$$$, $$$r$$$ such that $$$\frac{\prod_{i=l}^{r} a_i}{r-l+1}$$$ is maximum over all possible $$$l,r$$$ $$$(l \leq r)$$$.

Is it possible to solve this faster than $$$O(n^2)$$$? This problem looks like something well-known, but I am not sure.

Hello codeforces!

I am wondering is there a way to caculate prefix sums $$$k$$$ times modulo $$$p$$$ fast, especially when we can't use matrix multiplication?

By calculating prefix sums $$$k$$$ times I mean this piece of code:

for(int it = 0; it < k; it++) {
    for(int i = 1; i < n; i++)
        pref[i]+= pref[i-1];
}

So if we start with array: $$$1, 0, 0, 0$$$ we will get:

1. $$$1, 1, 1, 1$$$;

2. $$$1, 2, 3, 4$$$;

3. $$$1, 3, 6, 10$$$;

4. $$$1, 4, 10, 20$$$; ...