Delete Two Elements Educational Codeforces Round 115 Solution

Introduction

Educational Codeforces rounds are organized by Codeforces for the Division 2 Coders. Similarly Educational Codeforces Round was held on   Sunday, October 10, 2021 at 14:35UTC+5.5 

Series of Educational Rounds continue to be held as Harbour Space University initiative. This round will be rated for coders with rating upto 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the full correct solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution. You will be given 7 problems and two hours to solve them. 

The contest was a success and lots of submissions were made by the hard striving coders. Problem A that is the Computer Game was very easy and had the maximum number of successful submission. Problem B was a not easy but not difficult also it was fit for an average coder to solve. Problem C although was quite confusing at the start but it needed good logic to solve it. Problem D was medium to difficult if you spot the logic then it was not a very big deal. Problem E was difficult to understand but the announcement that was made during the contest helped to understand the problem but it was still difficult to solve as an average coder. Problem F and G were very difficult and were made for the top coders to solve although problem G had only 2 successful submission which decided the rankings of the contest.

This Educational Rounds are very beneficial for the coders who just have started their coding journey and are yet to understand difficult logics and algorithms. Thus practice properly and it would be a great deal to coding journey. 

Question

Monocarp has got an array a consisting of n integers. Let's denote k as the mathematic mean of these elements (note that it's possible that k is not an integer).

The mathematic mean of an array of n elements is the sum of elements divided by the number of these elements (i. e. sum divided by n).

Monocarp wants to delete exactly two elements from a$a$ so that the mathematic mean of the remaining (n−2)elements is still equal to k.

Your task is to calculate the number of pairs of positions [i,j] (i<j) such that if the elements on these positions are deleted, the mathematic mean of (n−2) remaining elements is equal to k (that is, it is equal to the mathematic mean of n elements of the original array a).

Input

The first line contains a single integer t (1≤t≤104) — the number of testcases.

The first line of each testcase contains one integer n (3≤n≤2⋅105) — the number of elements in the array.

The second line contains a sequence of integers a1,a2,…,an (0≤ai≤109), where ai is the i-th element of the array.

The sum of n over all testcases doesn't exceed 2⋅105

Output

Print one integer — the number of pairs of positions [i,j] (i<j) such that if the elements on these positions are deleted, the mathematic mean of (n−2) remaining elements is equal to k (that is, it is equal to the mathematic mean of n elements of the original array a).

Example

input

Copy

4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7

output

Copy

6
0
2
3

Note

In the first example, any pair of elements can be removed since all of them are equal.

In the second example, there is no way to delete two elements so the mathematic mean doesn't change.

In the third example, it is possible to delete the elements on positions 1 and 3, or the elements on positions 4 and 5.

Explanation

This question is easy but it takes some time to spot the logic. Take the inputs as per the problem. Calculate the sum of array of integers and multiply it by 2. If the sum is not divisible by nmuber of elements of array the print 0 otherwise take the quotient of sum divisble by number of elements. Now map the values according to the elements of array given in problem and calculate of sum of map of the elements and print that sum of maps. That's it now code it. I recommend not to directly visit the solution first try it yourself then take a look at the solution. 

Program Code

#include<bits/stdc++.h>

using namespace std;

#define ll long long

void solve(){

    int n;

    cin>>n;

    int arr[n];

    ll summ=0;

    map<int,int> m;

    for(int i=0;i<n;i++){

        cin>>arr[i];

        summ+=arr[i];

    }

    summ*=2;

    if(summ%n!=0){

        cout<<0<<endl;

        return;

    }

    summ/=n;

    ll ct=0;

    for(int i=0;i<n;i++){

        int x=summ-arr[i];

        ct+=m[x];

        m[arr[i]]++;

    }

    cout<<ct<<endl;

}

int main(){

    

    ll t=1;

    cin>>t;

    while(t--){

        solve();

    }

}

Thus we come to the end of this solution, hope you got benefit from this solution.