#输入整型数组和排序标识，对其元素按照升序或降序进行排序#

#include <bits/stdc++.h>
using namespace std;
void Heapify(vector<int>& nums, int i, int size, int flag) {
    int lastest = i;
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    if (flag == 0) {
        if (left < size && nums[left] > nums[lastest]) {
            lastest = left;
        }
        if (right < size && nums[right] > nums[lastest]) {
            lastest = right;
        }
    } else {
        if (left < size && nums[left] < nums[lastest]) {
            lastest = left;
        }
        if (right < size && nums[right] < nums[lastest]) {
            lastest = right;
        }
    }


    if (lastest != i) {
        swap(nums[i], nums[lastest]);
        Heapify(nums, lastest, size, flag);
    }
}



void buildHeap(vector<int>& nums, int flag) {
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; --i) {
        Heapify(nums, i, n, flag);
    }
    for (int i = n - 1; i >= 0; --i) {
        swap(nums[0], nums[i]);
        Heapify(nums, 0, i, flag);
    }
}
int main() {
    int x;
    int n;
    cin >> n;
    vector<int> nums;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        nums.push_back(x);
    }
    int flag;
    cin >> flag;
    buildHeap(nums, flag);
    for (auto& i : nums) {
        cout << i << " ";
    }

    return 0;
}
// 64 位输出请用 printf("%lld")