In this HackerEarth Xsquare And Number List problem solution Xsquare loves to play with numbers a lot. Today, he has a multi set S consisting of N integer elements. At first, he has listed all the subsets of his multi set S and later replaced all the subsets with the maximum element present in the respective subset.

Now, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.

To make this problem a bit more interesting, Xsquare decided to add Q queries to this problem. Each of the queries has one of the following type.

> K : Count the number of elements X in the final list such that X > K.
< K : Count the number of elements X in the final list such that X < K.
= K : Count the number of elements X in the final list such that X == K.

## HackerEarth Xsquare And Number List problem solution.

`#include <bits/stdc++.h>using namespace std ;#define LL long long int#define ft first#define sd second#define PII pair<int,int>#define MAXN 1000001#define mp make_pair#define f_in(st) freopen(st,"r",stdin)#define f_out(st) freopen(st,"w",stdout)#define sc(x) scanf("%d",&x)#define scll(x) scanf("%lld",&x)#define pr(x) printf("%d\n",x)#define pb push_back#define MOD 1000000007#define inf INT_MAX/2#define ASST(X,L,R) assert(X >= L && X <= R)int N,Q ;vector<int> A ;int power(int a,int b){    int res = 1 ;    while(b){        if(b%2){            res = (1LL * res * a) % MOD ;        }        b /= 2 ;        a = (1LL * a * a) % MOD ;    }    return res ;}int less_than_X(int X){    X -- ;    int c = upper_bound(A.begin(),A.end(),X)-A.begin() ;    return power(2,c) ;}int less_than_equals_to_X(int X){    int c = upper_bound(A.begin(),A.end(),X)-A.begin() ;    return power(2,c) ;}int main(){    sc(N) ;    sc(Q) ;    ASST(N,1,500000) ;    ASST(Q,1,500000) ;    A.resize(N) ;    for(int i=0;i<N;i++){        sc(A[i]) ;        ASST(A[i],1,1000000000) ;    }    sort(A.begin(),A.end()) ;    char ch ;    int X;    int total_subsets = power(2,N) ;    while(Q--){        cin >> ch ;        sc(X) ;        assert(ch == '>' || ch == '<' || ch == '=') ;        ASST(X,1,1000000000) ;        int ans = 0 ;        switch(ch){            case '<' : pr(less_than_X(X)) ;                        break ;            case '>' : ans = less_than_equals_to_X(X) ;                       ans = total_subsets - ans ;                       if( ans < 0 )                            ans += MOD ;                       pr(ans) ;                        break ;            case '=' : ans = less_than_equals_to_X(X) ;                       ans -= less_than_X(X) ;                       if( ans < 0 )                            ans += MOD ;                       pr(ans) ;                        break ;        }    }    return 0 ;}`

### Second solution

`#include <bits/stdc++.h>#define MAX 500005#define lli long long#define M 1000000007using namespace std;int A;lli pow2;void pre(){    pow2 = 1;    for ( int i = 1; i <= 500001; i++ ) {        pow2[i] = pow2[i-1] + pow2[i-1];        if ( pow2[i] >= M ) pow2[i] -= M;    }    return;}int main(){    pre();    int n,q,x;    char s;    scanf("%d%d", &n, &q);    assert(n<=500000);    assert(q<=500000);    for ( int i = 0; i < n; i++ ) {        scanf("%d", &A[i]);        assert(A[i] >= 1 && A[i]<=1000000000);    }    sort(A,A+n);    while ( q-- ) {        scanf("%s%d", &s, &x);        assert(x>=1&&x<=1000000000);        if ( s == '=' ) {            int idx2 = upper_bound(A,A+n,x) - A;            idx2--;            int idx1 = lower_bound(A,A+n,x) - A;            if ( idx1 == n || A[idx1] > x ) {                printf("0\n");                continue;            }            lli ans1 = pow2[idx1];            lli ans2 = pow2[idx2-idx1+1] - 1;            if ( ans2 < 0 ) ans2 += M;            printf("%lld\n", (ans1*ans2)%M);        }        else if ( s == '<' ) {            int idx = lower_bound(A, A+n, x) - A;            idx--;            lli ans1;            else ans1 = pow2[idx+1];            printf("%lld\n", ans1);        }        else {            int idx = upper_bound(A,A+n,x) - A;            lli ans1 = pow2[idx];            lli ans2 = pow2[n-idx] - 1;            if ( ans2 < 0 ) ans2 += M;            printf("%lld\n", (ans1*ans2)%M);        }    }    return 0;}`