#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<set>
#include<queue>
using namespace std;
void printArray(int* a,int n){
printf("%d",a[0]);
for(int i=1;i<n;i++){
printf(" %d",a[i]);
}
printf("\n");
return;
}
void sortCheck(int* a,int n);
void bogoBogoSort(int* a,int n){
bool isSorted;
do{
random_shuffle(a,a+n);
int chk[n];
copy(a,a+n,chk);
sortCheck(chk,n);
isSorted = true;
for(int i=0;i<n;i++){
if(a[i] != chk[i]){
isSorted = false;
break;
}
}
}while(!isSorted);
}
void sortCheck(int* a,int n){
if(n == 1){
return;
}
while(true){
bogoBogoSort(a,n-1);
if(a[n-2]<=a[n-1])return;
random_shuffle(a,a+n);
}
return;
}
int main(){
int NUM;
cin>>NUM;
int a[NUM];
srand(time(0));
for(int i=0;i<NUM;i++){
a[i] = rand();
}
printArray(a,NUM);
bogoBogoSort(a,NUM);
printArray(a,NUM);
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y3N0ZGxpYj4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8c3RyaW5nPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPHV0aWxpdHk+CiNpbmNsdWRlPHNldD4KI2luY2x1ZGU8cXVldWU+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBwcmludEFycmF5KGludCogYSxpbnQgbil7CgoJcHJpbnRmKCIlZCIsYVswXSk7Cglmb3IoaW50IGk9MTtpPG47aSsrKXsKCQlwcmludGYoIiAlZCIsYVtpXSk7Cgl9CglwcmludGYoIlxuIik7CgoJcmV0dXJuOwp9Cgp2b2lkIHNvcnRDaGVjayhpbnQqIGEsaW50IG4pOwoKdm9pZCBib2dvQm9nb1NvcnQoaW50KiBhLGludCBuKXsKCglib29sIGlzU29ydGVkOwoJZG97IAoJCXJhbmRvbV9zaHVmZmxlKGEsYStuKTsKCgkJaW50IGNoa1tuXTsKCQoJCWNvcHkoYSxhK24sY2hrKTsKCQkKCQlzb3J0Q2hlY2soY2hrLG4pOwoKCQlpc1NvcnRlZCA9IHRydWU7CgkJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJCWlmKGFbaV0gIT0gY2hrW2ldKXsKCQkJCWlzU29ydGVkID0gZmFsc2U7CgkJCQlicmVhazsKCQkJfQoJCX0KCgl9d2hpbGUoIWlzU29ydGVkKTsKCn0KCgp2b2lkIHNvcnRDaGVjayhpbnQqIGEsaW50IG4pewoKCWlmKG4gPT0gMSl7CgkJcmV0dXJuOwoJfQoKCXdoaWxlKHRydWUpewoJCWJvZ29Cb2dvU29ydChhLG4tMSk7CgkJCgkJaWYoYVtuLTJdPD1hW24tMV0pcmV0dXJuOwoJCXJhbmRvbV9zaHVmZmxlKGEsYStuKTsKCX0KCglyZXR1cm47Cn0KCmludCBtYWluKCl7CgoJaW50IE5VTTsKCWNpbj4+TlVNOwoJaW50IGFbTlVNXTsKCglzcmFuZCh0aW1lKDApKTsKCglmb3IoaW50IGk9MDtpPE5VTTtpKyspewoJCWFbaV0gPSByYW5kKCk7Cgl9CgoJcHJpbnRBcnJheShhLE5VTSk7CgoJYm9nb0JvZ29Tb3J0KGEsTlVNKTsKCglwcmludEFycmF5KGEsTlVNKTsKCglyZXR1cm4gMDsKfQo=