Untitled

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

// Function to swap elements
void swap(long long int *x, long long int *y) {
    long long int temp = *x;
    *x = *y;
    *y = temp;
}

// Function to check if two arrays are equal
bool isEqual(long long int *arr1, long long int *arr2, long long int len) {
    for (long long int i = 0; i < len; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

// Check if a permutation already exists in beautifulPerms
bool isUnique(long long int **beautifulPerms, long long int count, long long int *perm, long long int n) {
    for (long long int i = 0; i < count; i++) {
        if (isEqual(beautifulPerms[i], perm, n)) {
            return false; // Found a duplicate permutation
        }
    }
    return true; // No duplicate found
}

// Function to check if an array is beautiful
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;
}

// Generating permutations using Heap's algorithm
void generatePermutations(long long int arr[], long long int size, long long int n, long long int ***perms, long long int *count, long long int *capacity) {
    if (size == 1) {
        if (isBeautiful(arr, n) && isUnique(*perms, *count, arr, n)) {
            if (*count == *capacity) {
                *capacity *= 2;
                *perms = realloc(*perms, (*capacity) * sizeof(long long int*)); // Corrected
            }
            (*perms)[*count] = malloc(n * sizeof(long long int));
            for (long long int i = 0; i < n; i++) {
                (*perms)[*count][i] = arr[i];
            }
            (*count)++;
        }
    } else {
        for (long long int i = 0; i < size; i++) {
            swap(&arr[i], &arr[size - 1]);
            if (size==n || isBeautiful(arr, n - size + 1)) {
                generatePermutations(arr, size - 1, n, perms, count, capacity);
            }
            swap(&arr[i], &arr[size - 1]);  // backtrack
        }
    }
}

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

    long long int initialCapacity = 1;
    long long int **beautifulPerms = malloc(initialCapacity * sizeof(long long int*)); // Corrected
    long long int count = 0;
    generatePermutations(arr, N, N, &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;
}