/****************************************** * AUTHOR: CHIRAG AGARWAL * * INSTITUITION: BITS PILANI, PILANI * ******************************************/ #include using namespace std; typedef long long LL; typedef long double LD; const int MAX=1e5+5; const int LIM = 3e5 + 5; //equals 2 * 2^ceil(log2(n)) int arr[MAX]; int segmx[LIM]; int segmn[LIM]; int rgt[MAX]; int ad[MAX][30]; int rem[MAX][30]; vector vec; //Complexity: O(1) //Stores what info. segment[i..j] should store void combine(int t) { segmx[t] = max(segmx[t*2],segmx[t*2+1]); segmn[t] = min(segmn[t*2],segmn[t*2+1]); } //Complexity: O(n) void build(int t, int i, int j) { if (i == j) { //base case : leaf node information to be stored here segmn[t] = arr[i]; segmx[t]=arr[i]; return ; } int mid = (i + j) / 2; build(t*2, i, mid); build(t*2 + 1, mid + 1, j); combine(t); } //Complexity: O(log n) int querymx(int t, int i, int j, int l, int r) { if (i > r || j < l){ //base case: result of out-of-bound query return 0; } if (l <=i && j <= r) { return segmx[t]; } int mid = (i + j) / 2; int a = querymx(t*2, i, mid, l, r) ; int b = querymx(t*2 + 1, mid + 1, j, l, r); return max(a,b); } int querymn(int t, int i, int j, int l, int r) { if (i > r || j < l){ //base case: result of out-of-bound query return 1e9+5;; } if (l <=i && j <= r) { return segmn[t]; } int mid = (i + j) / 2; int a = querymn(t*2, i, mid, l, r) ; int b = querymn(t*2 + 1, mid + 1, j, l, r); return min(a,b); } int seg[LIM]; int lazy[LIM]; bool push[LIM]; //Complexity: O(1) //Stores what info. segment[i..j] should store void combinex(int t) { seg[t] = max(seg[t*2], seg[t*2+1]); } //Lazy propagation void propagate(int t, int i, int j) { if (push[t]) { seg[t] = max(seg[t],lazy[t]); if (i != j) { push[t*2] = true; push[t*2 + 1] = true; lazy[t*2] = max(lazy[t*2],lazy[t]); lazy[t*2 + 1] = max(lazy[t*2 + 1],lazy[t]); } push[t] = false; lazy[t] = 0; } } //Complexity: O(log n) void update(int t, int i, int j, int l, int r, int x) { propagate(t, i, j); if (i > r || j < l) { return ; } if (l <= i && j <= r) { //base case : leaf node information to be stored here lazy[t] = max(x,lazy[t]); push[t] = true; propagate(t, i, j); return ; } int mid = (i + j) / 2; update(t*2, i, mid, l, r, x); update(t*2 + 1, mid + 1, j, l, r, x); combinex(t); } //Complexity: O(log n) int query(int t, int i, int j, int l, int r) { propagate(t, i, j); if (i > r || j < l){ //base case: result of out-of-bound query return 0; } if (l <=i && j <= r) { return seg[t]; } int mid = (i + j) / 2; int a = query(t*2, i, mid, l, r) ; int b = query(t*2 + 1, mid + 1, j, l, r); return max(a, b); } int main() { int n,k; scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&arr[i]); } for(int i=1;i<=n;i++) { rgt[i]=-1; } build(1,1,n); for(int j=0;j<=29;j++) { ad[n+1][j]=n+1; rem[n+1][j]=n+1; } for(int i=n;i>=1;i--) { for(int j=0;j<=29;j++) { if((arr[i]>>j)&1) { ad[i][j]=i; rem[i][j]=rem[i+1][j]; } else { rem[i][j]=i; ad[i][j]=ad[i+1][j]; } } } for(int i=1;i<=n;i++) { vec.push_back(i); for(int j=0;j<=29;j++) { if((arr[i]>>j)&1) { vec.push_back(rem[i][j]); } else { vec.push_back(ad[i][j]); } } vec.push_back(n+1); sort(vec.begin(),vec.end()); auto it = std::unique (vec.begin(), vec.end()); vec.resize( std::distance(vec.begin(),it) ); int cor=0; int cand=(1<<30)-1; for(int j=0;j<(vec.size()-1);j++) { // printf("%d ",vec[j]); int u=arr[vec[j]]; cor|=u; cand&=u; int val=cor-cand; if(valreq) { hi=mid-1; } else { an=mid; lo=mid+1; } } rgt[i]=max(rgt[i],an); // printf("cam%d||",val); } vec.clear(); // printf("\n"); } for(int i=1;i<=n;i++) { if(rgt[i]!=-1) update(1,1,n,i,rgt[i],rgt[i]-i+1); } for(int i=1;i<=n;i++) { int x=query(1,1,n,i,i); if(x==0) { printf("-1\n"); } else { printf("%d\n",x); } } return 0; }