#include <stdio.h>
#include <stdlib.h>

#define MAXN 10000

// Node structure
typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

// Create a new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

// Comparator for qsort
int cmpfunc(const void* a, const void* b) {
    return ((int)a - (int)b);
}

// Build balanced BST recursively
Node* buildBalanced(int arr[], int l, int r) {
    if (l > r) return NULL;
    int mid = (l + r) / 2;
    Node* root = newNode(arr[mid]);
    root->left = buildBalanced(arr, l, mid - 1);
    root->right = buildBalanced(arr, mid + 1, r);
    return root;
}

// Print BST in required format (pre-order traversal)
void printBST(Node* root) {
    if (!root) return;
    int leftVal = root->left ? root->left->val : -1;
    int rightVal = root->right ? root->right->val : -1;
    printf("%d %d %d\n", root->val, leftVal, rightVal);
    printBST(root->left);
    printBST(root->right);
}

int main() {
    int N;
    if (scanf("%d", &N) != 1 || N < 1 || N > MAXN) {
        printf("Invalid input\n");
        return 0;
    }

    int arr[MAXN];
    for (int i = 0; i < N; i++) {
        if (scanf("%d", &arr[i]) != 1 || arr[i] < 1 || arr[i] > 100000) {
            printf("Invalid input\n");
            return 0;
        }
        // Check duplicates
        for (int j = 0; j < i; j++) {
            if (arr[j] == arr[i]) {
                printf("Invalid input\n");
                return 0;
            }
        }
    }

    // Sort numbers before building balanced BST
    qsort(arr, N, sizeof(int), cmpfunc);

    Node* root = buildBalanced(arr, 0, N - 1);

    printBST(root);

    return 0;
}