↵
#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;↵
}↵
↵
~~~~~↵
↵
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 Question id is [https://codeforces.com/contest/359/problem/D] and the solution i submitted is [https://codeforces.com/contest/359/submission/227495328]
