# HackerEarth Vanya and Array problem solution

In this HackerEarth Vanya and Array problem solution Let's define 2 functions a function F(i) and Val(i,j) for an Array A of size N as follows:

F(i) = Sigma(j=i+1, N) Val(i,j)

Val(i,j) = 1 ,if A[i] < A[j], else, Val(i,j) = 0.

Now, Vanya has been given one such array A of size N and an integer K. She needs to find the number of Distinct Unordered Pairs of elements (a,b) in array A such that F(a) + F(b) >= K.

## HackerEarth Vanya and Array problem solution.

`import java.io.*;import java.util.*;public final class vanya_and_array{    static long[] bit;    static int maxn=1000015;    static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));    static PrintWriter out=new PrintWriter(System.out);        static void update(int idx)    {        while(idx<maxn)        {            bit[idx]++;            idx+=idx&-idx;        }    }        static long query(int idx)    {        long sum=0;        while(idx>0)        {            sum=sum+bit[idx];            idx-=idx&-idx;        }        return sum;    }        public static void main(String args[]) throws Exception    {        int n=sc.nextInt(),k=sc.nextInt();        int[] a=new int[n],b=new int[n];bit=new long[maxn];        for(int i=0;i<n;i++)        {            a[i]=sc.nextInt();            b[i]=a[i];        }        Arrays.sort(b);        for(int i=0;i<n;i++)        {            a[i]=Arrays.binarySearch(b,a[i])+1;        }        long[] val=new long[n];        for(int i=n-1;i>=0;i--)        {            val[i]=query(maxn-1)-query(a[i]);            update(a[i]);        }        Arrays.sort(val);        long res=0;        for(int i=n-1;i>0;i--)        {            int low=1,high=i;            while(low<high)            {                int mid=(low+high+1)>>1;                if(val[i]+val[i-mid]>=k)                {                    low=mid;                }                else                {                    high=mid-1;                }            }            if(val[i]+val[i-low]>=k)            {                res=res+((i-1)-(i-low)+1);            }        }        out.println(res);        out.close();    }}class FastScanner{    BufferedReader in;    StringTokenizer st;    public FastScanner(BufferedReader in) {        this.in = in;    }        public String nextToken() throws Exception {        while (st == null || !st.hasMoreTokens()) {            st = new StringTokenizer(in.readLine());        }        return st.nextToken();    }        public String next() throws Exception {        return nextToken().toString();    }        public int nextInt() throws Exception {        return Integer.parseInt(nextToken());    }    public long nextLong() throws Exception {        return Long.parseLong(nextToken());    }    public double nextDouble() throws Exception {        return Double.parseDouble(nextToken());    }}`

### Second solution

`#include<bits/stdc++.h>using namespace std;int getSum(int BITree[], int index){    int sum = 0;    while (index > 0)    {        sum += BITree[index];        index -= index & (-index);    }    return sum;}void updateBIT(int BITree[], int n, int index, int val){    while (index <= n)    {       BITree[index] += val;       index += index & (-index);    }}void convert(int arr[], int n){    int temp[n];    for (int i=0; i<n; i++)        temp[i] = arr[i];    sort(temp, temp+n);int i;    for (i=0; i<n; i++)    {        arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;    arr[i]=n-arr[i]+1;  //changing largest element as smallest and so on, later we need to apply simple inversion count    }}int f[1000005];void getInvCount(int arr[], int n){    int invcount = 0;    convert(arr, n);    int BIT[n+1];    for (int i=1; i<=n; i++)        BIT[i] = 0;    for (int i=n-1; i>=0; i--)    {            f[i]= getSum(BIT, arr[i]-1);        updateBIT(BIT, n, arr[i], 1);    }}int main(){    int n,k,i,a[1000005];    scanf("%d%d",&n,&k);    for(i=0;i<n;i++)        scanf("%d",&a[i]);    getInvCount(a,n);    sort(f,f+n);long long count=0;    vector<int>v(f,f+n);    for(i=n-1;i>=0;i--)    {        int j=lower_bound(v.begin(),v.end(),k-v[i])-v.begin();        if(j!=n && j<i)            count+=i-j;    }    printf("%lld\n",count);    return 0;}`