#include "gondola.h" #include<bits/stdc++.h> using namespace std; int valid(int n, int a[]){ int cnt=0; for(int i=1;i<n;i++){ if(a[i]!=a[i-1]+1) cnt++; } return (cnt<=1); } //---------------------- int replacement(int n, int a[], int ans[]){ int apos=-1, av; int maxf=0; int minf = 0; unordered_map<int, int> m; for(int i=0;i<n;i++){ if(a[i]<=n) apos = i, av=a[i]; else m[a[i]] = i+1; maxf = max(maxf, a[i]); if(a[minf]>a[i]) minf = i; } if(apos==-1){ apos = minf; av = 1; } queue<int> q; int l=0; for(int i=n+1;i<=maxf;i++){ if(m[i]){ int c = l - 1; ans[l] = (n + av - (apos - m[i] + 1) - 1) % n + l - c; l++; //cout<<apos<<" "<<m[i]<<" "<<av<<endl; while(!q.empty()){ ans[l] = q.front(); q.pop(); l++; } } else q.push(i); } return l; } //---------------------- int countReplacement(int n, int a[]){ if(!valid(n, a)){ return 0; } sort(a, a+n); int ans=1; for(int i=0;i<n;i++){ if(a[i]<=n) continue; ans += max((a[i+1]-a[i]-3), 0); } return ans; }