1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100002;
const int mo = 1000000007;
int n,m,d[maxn],fact[maxn];
int locate(int x,int max)
{
    if(max<1 || x<d[1]) return 0;
    int l=1,r=max,mid;
    while(l<r)
    {
        if(l+1==r)
        {
            if(d[r]<=x) return r;
            else return l;
        }
        mid=(l+r)>>1;
        if(d[mid]==x) return mid;
        else
        if(d[mid]>x) r=mid-1;
        else l=mid;
    }
    
    if(d[l]<=x)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX