#include <bits/stdc++.h>
 #pragma GCC optimize ('O3,unroll-loops') 
 #pragma GCC target ("avx2")
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define ld long double
#define fuk return
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define pb push_back
#define tr(it,a) for(auto it=a.begin();it!=a.end();it++)
#define fo(i,n) for(int i=0;i<n;i++)
#define fop(i,x,n) for(int i=x;i<=n;i++)
#define forv(i,l,n) for(int i=l;i>=n;i--)
#define nl  << "\n";
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector < pair <ll,ll > > vp;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<string> vs;
#define inp(v, n) for(int i=0; i<n; ++i) cin >> v[i];
#define opt(v) for(auto x: v) cout << x << ' '; cout << endl;
const ll mod = 1000000007;
const ll N = 3e5+10;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
ll binpow(ll a, ll b) {
ll result = 1;
while (b > 0) {
if (b & 1)
result *= a;
        a *= a;
a %= mod;
b /= 2;
result %= mod;
}
return result;
}
ll n;
ll a[N];
multiset<ll> mt;
bool check(ll mid){
    mt.clear();
    fo(i,mid){
        mt.insert(a[i]);
    }
    fop(i,mid,n){
        ll mn=*mt.begin();
        // set<ll> st;
        ll cnt=0;

        // for(auto it=mt.begin();it!=mt.end();++it){
        //     st.insert(*it);
        // }
        for(ll j=mn;j<=1e7;j+=mn){
            // st.erase(st.find(j));
            cnt+=mt.count(j);
        }
        if(mt.size()==cnt){
            return true;
        }
        if(i!=n){
            mt.insert(a[i]);
            mt.erase(mt.find(a[i-mid]));
        }
    }
    return false;
}
void solve(){
    
    cin>>n;
    fo(i,n) cin>>a[i];
    ll mo=1e18;
    fo(i,n){
        mo=min(mo,a[i]);
    }
    if(mo==1){
        cout<<"1 "<<n-1 nl
        cout<<"1\n";
        return;
    }
    ll lo=1;
    ll hi=n;
    ll ans=1;
    //  cout<<"ho\n";
    while(hi>=lo){
        ll mid=(lo+hi)/2;
        // cout<<"hi\n";
        // lo=hi+1;
        if(check(mid)){
            ans=mid;
            lo=mid+1;
        }else{
            hi=mid-1;
        }
    }
    ll value=0;
    mt.clear();
    fo(i,ans){
        mt.insert(a[i]);
    }
    vl ind;
    fop(i,ans,n){
        ll mn=*mt.begin();
        // set<ll> st;
        ll cnt=0;

        // for(auto it=mt.begin();it!=mt.end();++it){
        //     st.insert(*it);
        // }
        for(ll j=mn;j<=1000004;j+=mn){
            // st.erase(st.find(j));
            cnt+=mt.count(j);
        }
        if(mt.size()==cnt){
            ind.push_back(i-ans+1);
            value++;
        }
        if(i!=n){
            mt.insert(a[i]);
            mt.erase(mt.find(a[i-ans]));
        }
    }
    sort(all(ind));
    cout<<value<<" ";
    cout<<ans-1 nl
    fo(i,ind.size()){
        cout<<ind[i]<<" ";
    }cout nl

}
signed main(){
    IOS
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    solve();
    return 0;
}

https://mirror.codeforces.com/contest/359/submission/227495328 The question id is: https://mirror.codeforces.com/contest/359/problem/D Here I have used a simple binary search which is overall giving time complexity (o(n)logn) there is sieve technique used in code which can compute in O(nlog log n) time so overall the entire code wont take more than O(nlogn) as per me . Please Correct me if there is some mistake.

https://mirror.codeforces.com/contest/245/submission/208958601 soln link // https://mirror.codeforces.com/contest/245/problem/H problem link//

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define ld long double
#define pb push_back
#define tr(it,a) for(auto it=a.begin();it!=a.end();it++)
#define fo(i,n) for(int i=0;i<n;i++)
#define fop(i,x,n) for(int i=x;i<=n;i++)
#define forv(i,l,n) for(int i=l;i>=n;i--)
#define nl <<endl;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<string> vs;
#define inp(v, n) for(int i=0; i<n; ++i) cin >> v[i];
#define opt(v) for(auto x: v) cout << x << ' '; cout nl
const ll mod = 1000000007;
const ll N = 2e5+10;
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
void solve(){
    
    string s;
    cin>>s;
    ll q;
    cin>>q;
    ll n=s.size();
    bool dp[n+3][n+3];
   fo(i,n+3){
    fo(j,n+3){
        dp[i][j]=false;
    }
   }
    for(int l=n-1;l>=0;--l){
        fo(r,n){
            if(l>r) continue;
            ll len=r-l+1;
            if(len==1) dp[l][r]=true;
            else if(len==2 && s[l]==s[r]) dp[l][r]=true;
            else if(s[l]==s[r] && dp[l+1][r-1]){
                dp[l][r]=true;
            }
            else{
                dp[l][r]=false;
            }
        }
    }
    ll cnt[n+1][n+1];
    fo(i,n+1){
        fo(j,n+1){
            cnt[i][j]=0;
        }
    }
    fo(i,n){
        ll sm=0;
        for(int j=i;j<n;++j){
            if(dp[i][j]){
                sm++;
            }
            cnt[i][j]=sm;
        }
    }
    fo(j,n){
        fop(i,1,n-1){
            cnt[i][j]=cnt[i-1][j]+cnt[i][j];
        }
    }
    while(q--){
        ll a,b;
        cin>>a>>b;
        ll ans=0;
        a--;
        b--;
 
        // fop(i,a,b){
        //     ans+=cnt[i][b];
        // }
        if(a==0)
        ans=cnt[b][b];
        else{
           ans= cnt[b][b]-cnt[a-1][b];
        }
        cout<<ans<<endl;
        // fop(j,a,b){
        //     ans+=cnt[]
        // }
    }
}
signed main(){
    IOS
    ll t=1;
    while(t--) solve();
    return 0;
}