using namespace std;
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <string>

int a[1000001],b[1000001];
int n;

void init()
{
    srand(time(0));
    n=1000000;
    for(int i=1;i<=n;++i) a[i]=rand()%2000000001;
}

inline int bs1(int v)
{
    int i,cnt;
    for(i=1, cnt=(1<<20);cnt; cnt>>=1)
	if(i+cnt<=n)
	    if(a[i+cnt]<=v) i+=cnt;
    if(a[i]==v)return 1;
    return 0;
}

inline int bs2(int v)
{
    int l=1,r=n, m;

    while(l<=r)
    {
	
	int m=(l+r)>>1;
	if(a[m]==v)return 1;
	else if(v<a[m]) r=m-1;
	else if(v>a[m]) l=m+1;
	
    }
    return 0;
}

//radix-sort
inline void rad(int n, int byte, int a[], int b[])
{
    int count[256], index[256],i;
    memset(count, 0, sizeof(count));
    for(i=1;i<=n;++i) ++count[(a[i]>>byte)&255];
    index[0]=1;
    for(i=1;i<256;++i) index[i]=index[i-1]+count[i-1];
    for(i=1;i<=n;++i) b[index[(a[i]>>byte)&255]++]=a[i];
}

inline void radix_sort(int n, int a[])
{
    rad(n, 0, a, b);
    rad(n, 8, b, a);
    rad(n, 16, a, b);
    rad(n, 24, b, a);
   //for(int i=1;i<=n;++i) a[i]=b[i];
}

inline int isok(int a[], int n)
{
    for(int i=2;i<=n;++i)
	if(a[i]<a[i-1]) return 0;
    return 1;
}

int main()
{
    init();


   
   radix_sort(n,a); 
  // sort(a+1,a+n+1);

//    printf("%d\n", isok(a, n));   

    int m=1000000, v;


    while(m--)
    {
	v=rand();

    bs1(v);
//	binary_search(a+1,a+n+1,v);
   // if(    bs1(v) != binary_search(a+1,a+n+1,v)) printf("damn\n");
    }



    return 0;
}