Gym 101848B

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;

ll a[N];
map<ll,int>mp;

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int n;r(n);
    for(int i=1;i<=n;++i){
        r(a[i]);
    }
    if(n<=15){
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if((a[j]-a[i])%(j-i))continue;
                else {
                    ll d=(a[j]-a[i])%(j-i);
                    int cnt=0;
                    for(int k=1;k<=n;++k){
                        cnt+=(a[k]!=a[i]+d*(k-i));
                    }
                    if(cnt<=3){
                        for(int k=1;k<=n;++k){
                            printf("%lld ",a[i]+d*(k-i));
                        }
                        puts("");
                        return 0;
                    }
                }
            }
        }
    }
    for(int i=1;i<n;++i){
        mp[a[i+1]-a[i]]++;
    }
    int mx=0;
    ll d;
    for(map<ll,int>::iterator it=mp.begin();it!=mp.end();it++){
        if(mx<it->second){
            mx=it->second;
            d=it->first;
        }
    }
    for(int i=1;i<n;++i){
        if(a[i+1]-a[i]==d){
            int cnt=0;
            for(int k=1;k<=n;++k){
                cnt+=(a[k]!=a[i]+d*(k-i));
            }
            if(cnt<=3){
                for(int k=1;k<=n;++k){
                    printf("%lld ",a[i]+d*(k-i));
                }
                puts("");
                return 0;
            }
        }
    }
    return 0;
}