### PROBLEM LINK:

**Author & Editoralist:** Jafar Badour

**Tester:** Teja Reddy

### PROBLEM EXPLANATION

Almir had a small sequence A_1, A_2, \ldots, A_N. He decided to make K copies of this sequence and concatenate them, forming a sequence X_1, X_2, \ldots, X_{NK}; for each valid i and j (0 \le j \lt K) :: X_{j \cdot N + i} = A_i.

For example, if A = (1, 2, 3) and K = 4, the final sequence is X = (1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3).

A pair (i, j), where 1 \le i \lt j \le N, is an inversion if X_i \gt X_j. Find the number of inversions in the final sequence X.

1 \leq N \leq 100

### DIFFICULTY:

Easy

### PREREQUISITES:

None

### EXPLANATION:

Find inversions count in our starting array A. This can be done in O(N^2) easily with 2 loops and letâ€™s denote this count with P.

Clearly, since we are gonna repeat the same array K times, we would have P*K inversions.

What else should we consider?

We should consider inversions resulting from two elements with indices a,b belonging to 2 different pieces (by piece we mean one of the concatenated arrays).

The number of inversions resulting from concatenating A with itself (once) is equal to the number of pairs of different numbers in a single copy of A. Letâ€™s denote this count with Q.

When appending the i_{th} copy of A to our final array X our answer would increase by (i-1)*Q

ans = P*K + \sum_{i=1}^{i=K-1} Q

ans = P*K+K*(K-1)/2*Q

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int T , n , K;
int arr[200];
int main(){
cin>>T;
while(T--){
cin>>n>>K;
int a = 0 , b = 0;
for(int j = 1 ; j <= n ; j++){
cin>>arr[j];
for(int i = 1 ; i < j ; i++){
if(arr[i] != arr[j]) ++a;
if(arr[i] > arr[j]) ++b;
}
}
cout<<1ll * K * b + 1ll * a * K * (K - 1) / 2<<endl;
}
}
```