#include <random>

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>

using namespace std;

template <typename T>
ostream& operator << (ostream& os, const vector<T>& v) {
    for (const auto& c : v)
        os << c << " ";
    return os;
}

template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end) {
    if (distance(range_begin, range_end) < 2)
        return;
    vector<typename RandomIt::value_type> v(range_begin, range_end);

    auto middle = v.begin() + v.size()/2;
    MergeSort(v.begin(), middle);
    MergeSort(middle, v.end());
    merge(v.begin(), middle, middle, v.end(), range_begin);
}

//template <typename RandomIt>
//void MergeSort(RandomIt range_begin, RandomIt range_end) {
//    if (distance(range_begin, range_end) < 2)
//        return;
//    vector<typename RandomIt::value_type> v(range_begin, range_end);
//
//    auto one = v.begin() + v.size()/3;
//    auto two = one + v.size()/3;
//    MergeSort(v.begin(), one);
//    MergeSort(one, two);
//    MergeSort(two, v.end());
//    vector<typename RandomIt::value_type> v1;
//    merge(v.begin(), one, one, two, back_inserter(v1));
//    merge(v1.begin(), v1.end(), two, v.end(), range_begin);
//}

//template <typename RandomIt>
//void MergeSort(RandomIt range_begin, RandomIt range_end) {
//    if (distance(range_begin, range_end) < 2) {
//        return;
//    }
//    auto middle = range_begin + distance(range_begin, range_end)/2;
//    MergeSort(range_begin, middle);
//    MergeSort(middle, range_end);
//    auto first1 = range_begin, last1 = middle, first2 = middle, last2 = range_end;
//    while (first1 != last1) {
//        if (first2 == last2)
//            break;
//        if (*first2 < *first1) {
//            swap(first1, first2);
//
//        }
//    }
//}
//
int main() {
    int N;
    cin >> N;
    vector<int> v(N);
    iota(v.begin(), v.end(), 1);
    shuffle(v.begin(), v.end(), std::mt19937(std::random_device()()));
    cout << v << endl;
    MergeSort(v.begin(), v.end());
    cout << v << endl;
    return 0;
}