#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <sys/time.h>
#include <set>
#include <assert.h>
FILE *fin, *fout;
struct Treap{
int key, priority;
int sz;
Treap *left;
Treap *right;
};
int get_sz(Treap *t) {
if(t == nullptr)
return 0;
return t->sz;
}
void rebuild(Treap *t) {
if(t == nullptr)
return;
t->sz = 1 + get_sz(t->left) + get_sz(t->right);
}
std::pair<Treap*, Treap*> split(Treap *t, int key) {
if(t == nullptr) {
return {nullptr, nullptr};
}else if(t->key <= key) {
auto [first, second] = split(t->right, key);
t->right = first;
rebuild(t);
rebuild(second);
return {t, second};
}else {
auto [first, second] = split(t->left, key);
t->left = second;
rebuild(t);
rebuild(first);
return {first, t};
}
}
Treap* merge(Treap *left, Treap* right) {
if(left == nullptr) {
return right;
}
else if(right == nullptr) {
return left;
}
else if(left->priority > right->priority) {
left->right = merge(left->right, right);
rebuild(left);
return left;
} else {
right->left = merge(left, right->left);
rebuild(right);
return right;
}
}
Treap *insert(Treap *t, Treap *nd) {
if(t == nullptr) {
return nd;
}
if(nd->priority > t->priority) {
auto [first, second] = split(t, nd->key);
nd->left = first;
nd->right = second;
rebuild(nd);
return nd;
}
if(t->key >= nd->key) {
t->left = insert(t->left, nd);
rebuild(t);
return t;
}else {
t->right = insert(t->right, nd);
rebuild(t);
return t;
}
}
Treap *insert(Treap *t, int key) {
return insert(t, new Treap{
.key = key,
.priority = rand(),
.sz = 1,
.left = nullptr,
.right = nullptr
});
}
Treap *erase(Treap *t, int key) {
if(t == nullptr){
return nullptr;
}
if(t->key == key) {
t = merge(t->left, t->right);
rebuild(t);
return t;
}
if(key <= t->key) {
t->left = erase(t->left, key);
rebuild(t);
return t;
}
if(key > t->key) {
t->right = erase(t->right, key);
rebuild(t);
return t;
}
}
bool empty(Treap *t) {
return (t == nullptr);
}
bool find_key(Treap *t, int key) {
if(t == nullptr)
return false;
if(key == t->key)
return true;
return find_key(key <= t->key ? t->left : t->right, key);
}
int order_of_key(Treap *t, int key) {
if(t == nullptr)
return 0;
if(t->key == key) {
return get_sz(t->left);
}if(t->key > key) {
return order_of_key(t->left, key);
}else if(t->key < key){
return get_sz(t->left) + 1 + order_of_key(t->right, key);
}
}
int find_by_order(Treap *t, int k) {
if(t == nullptr)
return -1;
if(k < get_sz(t->left)) {
return find_by_order(t->left, k);
}else if(k == get_sz(t->left))
return t->key;
else {
return find_by_order(t->right, k - get_sz(t->left) - 1);
}
}
int main() {
fin = fopen("order.in", "r");
fout = fopen("order.out", "w");
int n;
fscanf(fin, "%d", &n);
Treap *treap = nullptr;
for( int i = 1; i <= n; i++ ) {
treap = insert(treap, i);
}
int poz = 1;
int i = 1;
while(!empty(treap)) {
poz %= get_sz(treap);
int x = find_by_order(treap, poz);
treap = erase(treap, x);
fprintf(fout, "%d ", x);
poz += i++;
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}