`#include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
const int M = 1e9 + 7;

int a[N];
bool st[N];
int b[N];
bool is_prime(int x)
{
if(x == 1 || x == 0) return false;

for(int i = 2; i <= x / i; i ++)
{
    if(x % i == 0) return false;
}


return true;

}
int main()
{
int n, q;
cin >> n >> q;

    int cnt = 0;
    for(int i = 2; i <= n; i ++)
    {   
        if(!st[i])
        {
            a[cnt ++] = i;
        }

        for(int j = 0; a[j] <= n / i; j ++)
        {
            st[a[j] * i] = true;
            if(i % a[j] == 0) break;
        }
    }
    st[0] = st[1] = 1;
    int g[N];
    memset(g, 0, sizeof(g));
    for(int i = 2; i <= n; i ++)
    {   
        g[i] = g[i - 1];
        if(!st[i] && !st[i / 2])
        {   
            g[i] ++;
        }
    }

while(q --)
{
    int l, r;
    cin >> l >> r;


    //for(int i = 2; i <= n; i ++) cout << g[i] << " ";
    //cout << endl;
    cout << g[r] - g[l - 1] << endl;
}

}
/////埃拉托色尼筛法
for(int i = 2; i * i<= n; i ++)
{
if(!st[i])
{
for(int j = i * i; j <= n; j += i)
{
st[j] = true;
}
}
}
`

`#include [HTML_REMOVED]

using namespace std;
const int N = 2e7 + 10;
typedef long long LL;

LL f[N];
int min_num[N];
int prime[N];
bool st[N];
//这里数据量较大 无法简单用一个数据来进行求解 只能用空间换时间 利用前缀和进行优化 找出每个数的最小质因数
void fun(int n)
{

int cnt = 0;
for(int i = 2; i <= n; i ++)
{
    if(!st[i])
    {
        prime[cnt ++] = i;
        min_num[i] = i;
    }
    for(int j = 0; prime[j] * i <= n; j ++)
    {
        st[prime[j] * i] = true;
        min_num[prime[j] * i] = prime[j];
        if(i % prime[j] == 0) break; 
    }
}
min_num[1] = 0, f[0] = 0;
for(int i = 1; i <= n; i ++) f[i] = f[i - 1] + min_num[i];

}
int main()
{
int t;
cin >> t;

fun(2e7 + 10);

while(t --)
{
    int n;
    cin >> n;

    cout << f[n] << endl;
}

}`

`#include [HTML_REMOVED]

using namespace std;

const int N = 7e5 + 10;

typedef long long LL;

LL h[N], st[N];
int l[N], r[N];

int main()
{
int n;
cin >> n;
//单调栈 注意点 题目所求的是该楼层所在位置 因此在具体存放的数据时需要注意 不要存入楼层高度这一值 此外 这里所求的是左边楼层较低的位置
for(int i = 1; i <= n; i ++ ) cin >> h[i];

int top = 0;
for(int i = 1; i <= n; i ++)
{
    while(top && h[st[top]] <= h[i]) top --;
    if(!top) l[i] = -1;
    else l[i] = st[top];

    st[++ top] = i;
}

top = 0;
for(int i = n; i >= 1; i --)
{
    while(top && h[st[top]] <= h[i]) top --;
    if(!top) r[i] = -1;
    else r[i] = st[top];

    st[++ top] = i;
}

for(int i = 1; i <= n; i ++) cout << l[i] << " ";
cout << endl;
for(int i = 1; i <= n; i ++) cout << r[i] << " ";

}`

`#include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 7e5 + 10;
const int M = 998244353;
typedef long long LL;

LL h[N], st[N];
int l[N], r[N];

LL min_num[N], max_num[N];
//快速幂
LL pmi(LL a, LL b, LL p)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;

    b = b >> 1;

    a = a * a % p;
}

return res;

}
int main()
{
int n, k, x;
cin >> n >> k >> x;

for(int i = 1; i <= n; i ++) cin >> h[i];



int tt = 0, hh = 1;

LL cnt1 = 0;
//单调队列模拟滑动窗口
for(int i = 1; i <= n; i ++)
{
    while(tt >= hh && i - l[hh] + 1 > k) hh ++;
    while(tt >= hh && h[l[tt]] >= h[i]) tt --;
    l[++ tt] = i;
    if(i - k >= 0) min_num[cnt1 ++] = h[l[hh]] ;
}

tt = 0, hh = 1;

LL cnt2 = 0;
for(int i = 1; i <= n; i ++)
{
    while(tt >= hh && i - r[hh] + 1 > k) hh ++;
    while(tt >= hh && h[r[tt]] <= h[i]) tt --;
    r[++ tt] = i;
    if(i - k >= 0)
    {   
        max_num[cnt2 ++] = h[r[hh]] ;
    }
}
LL ans = 0;
for(int i = 0; i < cnt1; i ++)
    if(max_num[i] - min_num[i] <= x) ans ++;

LL sum = n - k + 1;

//cout << ans << " " << sum;
//快速幂求逆元
cout << ans * pmi(sum, M - 2, M) % M;

}`