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;
    for (long long int i = 0; i < n - 2; i++) {
        long long int diff1 = arr[i + 1] - arr[i];
        long long int diff2 = arr[i + 2] - arr[i + 1];
        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 used[], long long int index, long long int ***perms, long long int *count, long long int *capacity) {
    if (index == n) {
        // Found a beautiful permutation
        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] = used[i];
        }
        (*count)++;
        return;
    }

    for (long long int i = 0; i < n; i++) {
        bool alreadyUsed = false;
        for (long long int j = 0; j < index; j++) {
            if (used[j] == arr[i]) {
                alreadyUsed = true;
                break;
            }
        }
        if (!alreadyUsed) {
            used[index] = arr[i];
            if (isBeautiful(used, index + 1)) {
                generatePermutations(arr, n, used, index + 1, perms, count, capacity);
            }
            // No need to explicitly backtrack as used[index] will be overwritten in the next iteration
        }
    }
}

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], used[N];
    for (long long int i = 0; i < N; i++) {
        scanf("%lld", &arr[i]);
        used[i] = 0;
    }

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

    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;
}