Untitled

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

bool isBeautiful(long long int arr[], long long int n) {
    if (n < 3) return true;

        long long int diff1 = arr[n-2] - arr[n-3];
        long long int diff2 = arr[n-1] - arr[n-2];
        if ((diff1 >= 0 && diff2 >= 0) || (diff1 <= 0 && diff2 <= 0)) return false;

    return true;
}

void generatePermutations(long long int arr[], long long int n, long long int temp[], long long int index, long long int ***perms, long long int *count, long long int *capacity, bool usedIndex[]) {
    if (index == n ) {
            if (*count == *capacity) {
                *capacity *= 2;
                *perms = realloc(*perms, (*capacity) * sizeof(long long int *));
            }
            (*perms)[*count] = malloc(n * sizeof(long long int));
            for (long long int i = 0; i <
             n; i++) {
                (*perms)[*count][i] = temp[i];
            }
            (*count)++;

        return;
    }

    for (long long int i = 0; i < n; i++) {
        if (!usedIndex[i] && (i == 0 || arr[i] != arr[i - 1] || usedIndex[i - 1])) {
            usedIndex[i] = true;
            temp[index] = arr[i];
            if(isBeautiful(temp,index+1)) generatePermutations(arr, n, temp, index + 1, perms, count, capacity, usedIndex);
            usedIndex[i] = false;
        }
    }
}

int compare(const void *a, const void *b) {
    long long int *arr1 = *(long long int**)a;
    long long int *arr2 = *(long long int**)b;
    long long int n = 0;
    while (arr1[n] == arr2[n]) n++;
    return arr1[n] - arr2[n];
}

int main() {
    long long int N;
    scanf("%lld", &N);
    long long int arr[N], temp[N];
    bool usedIndex[N];
    for (long long int i = 0; i < N; i++) {
        scanf("%lld", &arr[i]);
        temp[i]=0;
        usedIndex[i] = false;
    }

    long long int initialCapacity = 1;
    long long int **beautifulPerms = malloc(initialCapacity * sizeof(long long int *));
    long long int count = 0;
    generatePermutations(arr, N, temp, 0, &beautifulPerms, &count, &initialCapacity, usedIndex);

    qsort(beautifulPerms, count, sizeof(long long int *), compare);

    printf("%lld\n", count);
    
    for (long long int i = 0; i < count; i++) {
        for (long long int j = 0; j < N; j++) {
            printf("%lld ", beautifulPerms[i][j]);
        }
        printf("\n");
        free(beautifulPerms[i]);
    }
    free(beautifulPerms);

    return 0;
}