# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

**Setter:** Kanhaiya Mohan

**Tester:** Nishant Shah

**Editorialist:** Bhavya Mittal

# DIFFICULTY

Easy

# PREREQUISITES

None

# PROBLEM

Given an array A of length N. You need to rearrange the elements of A such that:

- the value of the element decreases by 1 upon visiting.
- the number of elements visited is maximum
- elements are visited in circular order until 0 is encountered

# EXPLANATION

**Observation 1**

The first zero will be encountered at one of the minimum values of the array.

## Proof

Since each element decreases by 1 upon visiting and we are traversing the array in a circular fashion, the first element where we will encounter 0 will be one of the minimums.

Since we can rearrange the elements in any order, we sort the array in increasing order, so that all the minimum elements come together in one place.

**Observation 2**

If we complete one loop on the whole array then the value of every element decreases exactly by 1.

**Observation 3**

We can traverse through the array at a[0] (of the sorted array) times, i.e. we can visit at least a[0] * N elements.

## Proof

Letâ€™s take an example to understand this point:

Let the sorted array be [2, 2, 3, 5, 6]

After 1 traversal: [1, 1, 2, 4, 5] Elements visited = 5

After 2 traversals: [0, 0, 1, 3, 4] Elements visited = 5

Total elements visited = 5 + 5 = 2 * 5

Since the first element has become$ 0$, we canâ€™t traverse the array any more.

Now, to maximize the number of elements visited we can start our traversal from the element next to the element with the minimum value, which isnâ€™t equal to it.

Letâ€™s say that value is at index i, then our final answer = a[0] * N + (N - i).

To understand this letâ€™s take the above example again.

The sorted array: [2, 2, 3, 5, 6]

We start our traversal from 3.

After 1 traversal: [2, 2, 2, 4, 5]. Elements visited = 3.

The remaining 2 traversals are the same.

Total elements visited = 2 * 5 + 3.

# SOLUTIONS

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int n;
void solve()
{
cin >> n;
long long int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
int ans = 0;
int mn = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > mn)
{
cout << a[0] * n + n - i;
return;
}
}
cout << a[0] * n;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
cout << "\n";
}
return 0;
}
```