# Square Game

QUESTION

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.\nFor example :\nConsider the following multi set consisting of 3 elements S = {1,2,3}. \nList of all subsets:\n{}\n{1}\n{2}\n{3}\n{1,2}\n{2,3}\n{1,3}\n{1,2,3}\nFinal List:\n{0}\n{1}\n{2}\n{3}\n{2}\n{3}\n{3}\n{3}\nNow, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.\nTo 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.\n > K : Count the number of elements X in the final list such that X > K.\n < K : Count the number of elements X in the final list such that X < K.\n = K : Count the number of elements X in the final list such that X == K.\nNote:\n Answer to a particular query can be very large. Therefore, Print the required answer modulo 109+7.\n An empty subset is replaced by an integer 0.\nInput\nFirst line of input contains two space separated integers N and Q denoting the size of multiset S and number of queries respectively. Next line of input contains N space separated integers denoting elements of multi set S. Next Q lines of input contains Q queries each having one of the mentioned types.\nOutput\nFor each query, print the required answer modulo 109+7.\n.

“TESTCASE_1”: “3 5\n1 2 3\n< 1\n> 1\n= 3\n= 2\n> 3\n###—###SEPERATOR—###—\n1\n6\n4\n2\n0”, “TESTCASE_2”: “3 5\n2 3 4\n< 2\n> 3\n= 1\n= 2\n> 2\n###—###SEPERATOR—###—\n1\n4\n0\n1\n6”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;

ll power(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b/=2;
}
return res;
}
int main()
{
ll n,q,i,ans,ans1;
scanf("%lld%lld",&n,&q);
ll arr[n];
for(i=0;i<n;i++)
scanf("%lld",&arr[i]);
ll x,l,r;
char ch;
sort(arr,arr+n);
while(q--)
{
cin>>ch;
scanf("%lld",&x);
// cout<<ch;
if(ch=='=')
{
r=upper_bound(arr,arr+n,x)-arr;
ans1=(power(2,n)-power(2,r)+mod+mod)%mod;
x--;
l=upper_bound(arr,arr+n,x)-arr;
ans=power(2,l);
ans=(power(2,n)-ans-ans1+mod+mod)%mod;
// cout<<l<<" "<<r<<" "<<(r-l+1)<<endl;
//ans=power(2,r-l+1);
}
else if(ch=='<')
{
x--;
r=upper_bound(arr,arr+n,x)-arr;
ans=(power(2,r)+mod)%mod;
// cout<<r<<endl;
}
else
{
r=upper_bound(arr,arr+n,x)-arr;
ans=(power(2,n)-power(2,r)+mod+mod)%mod;
//cout<<r<<endl;
}
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
}``````