#include <stdio.h>

int main(void) {
    int N[10], P[10];
    int Top;
    int num, i, prv, cur;

    Top = -1;

    /* 配列初期化 */
    for (i = 0; i < 10; i++) {
        N[i] = -1;
        P[i] = -1;
    }

    i = 0;

    printf("数値を入力 (-1で終了): ");
    scanf("%d", &num);

    while (num != -1 && i < 10) {

        N[i] = num;

        prv = -1;
        cur = Top;

        /* 大きい順になる位置を探す */
        while (cur != -1 && (N[i] > N[cur])) {
            prv = cur;
            cur = P[cur];
        }

        P[i] = cur;

        if (prv != -1) {
            P[prv] = i;
        } else {
            Top = i;
        }

        i++;

        printf("数値を入力 (-1で終了): ");
        scanf("%d", &num);
    }

    /* 表示 */
    cur = Top;

    printf("並び替え結果:\n");

    while (cur != -1) {
        printf("%d\n", N[cur]);
        cur = P[cur];
    }

    return 0;
}