Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Tourist ( Gennady Korotkevich ) is a famous competitive programmer. He has won two ACM ICPC World Finals. Thanks to his sublime performance in contests, he has become very popular all over the world!

One day Tourist came across an interesting problem. It goes like this:

You are given an array **A** of **N** integers named **A0 , A1 , ... , AN-1**. The array elements are in the range **[0,N-1]**. You have to rearrange the elements in a non-decreasing order. Let **Pi** denote the location of the value **Ai** after the rearrangement is done. The cost of this rearrangement is the sum of **| Pi - i |** for all **0 ≤ i ≤ N-1**. Here, **|x|** denotes the absolute value of **x**. You have to find the minimum cost of such a rearrangement.

These days Tourist is too busy playing the new arcade game, **Forthright** on his dearest gaming PC. So he asks you, his favorite underling, to solve this problem.

The first line of input contains an integer **T**, the number of test cases for the problem. Each of the following **T** lines describe a test case.

For each test case, you are given four integers in the following order: **N** (the number of elements in array **A**), **A0** (the first element of array **A**), **B** and **C**. **Ai** for **1 ≤ i ≤ N-1** is calculated using the formula **Ai = ( ( Ai-1 * B ) + C ) % N**.

**1 ≤ T ≤ 104****1 ≤ N ≤ 104****0 ≤ Ai < N** for all **0 ≤ i < N****0 ≤ B, C ≤ 109**

Notice that both the initial array and the array after rearrangement have **0-based** indexing.

For each test case, output the minimum cost of rearrangement for that case in a separate line.

Please take a look at the sample input/output to get a better understanding of the format.

Input | Output |
---|---|

2 4 3 5 3 4 0 1 1 | 8 0 |

Case 01:

Before rearrangement, A = [ 3, 2, 1, 0 ]

After rearrangement, A = [ 0, 1, 2, 3]

P = [ 3, 2, 1, 0 ]. Hence, cost = | 3 – 0 | + | 2 – 1 | + | 1 – 2 | + | 0 – 3 | = 8.

Case 02:

Before rearrangement, A = [ 0, 1, 2, 3 ]

After rearrangement, A = [ 0, 1, 2, 3]

P = [ 0, 1, 2, 3 ]. Hence, cost = | 0 – 0 | + | 1 – 1 | + | 2 – 2 | + | 3 – 3 | = 0.

52% Solution Ratio

PsychoKillerEarliest,

ovis96Fastest, 1380672.9s

ovis96Lightest, 262 kB

MistiiShortest, 610B

Login to submit

We need to sort the given array elements. In order to reduce the cost, we must do an "in place&...

Toph uses cookies. By continuing you agree to our Cookie Policy.