Split in Three

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
using namespace std;
const int N=101019;
int ans[N];
int sum[4];
int c[N];
bool SOLVED=false;
void F(int pos,int n){
    if (SOLVED) return;
    if (pos==n+1){
        if (sum[1]+1==sum[2] && sum[2]+1==sum[3]){
            for (int i=1;i<=n;i++) ans[i]=c[i];
            SOLVED=true;
        }
        return;
    }
    for (int i=1;i<=3;i++){
        c[pos]=i;
        sum[i]+=pos;
        F(pos+1,n);
        sum[i]-=pos;
        c[pos]=0;
    }
}
void solve(){
    int n;cin>>n;
    int nn=n;
    int sum=n*(n+1)/2;
    if (sum%3){
        cout<<"IMPOSSIBLE\n";
        return;
    }
    while (n>=9){
        ans[n]=1;
        ans[n-1]=2;
        ans[n-2]=3;
        ans[n-3]=3;
        ans[n-4]=2;
        ans[n-5]=1;
        n-=6;
    }
    F(1,n);
    if (!SOLVED) exit(1);
    for (int i=1;i<=nn;i++) cout<<ans[i]<<" ";
    cout<<endl;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
    while (tt--){
        solve();
    }
    return 0;
}

//1 2 3 3 2 1
//1 (1) 3 (1) 5 6
//6 7 8
//1 2 3 4 5 6

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED