Включить элемент в упорядоченный по убыванию массив, не нарушая упорядоченности - C (СИ)

#include <stdio.h>
#include <stdlib.h>
//Задан упорядоченный по убыванию массив F=F(i), i=1,2,...N. Включить число Z
//в массив F, не нарушая упорядоченности. Вывести полученный массив F=F(i), i=1,2,...,N+1
void Sort_on_decrease(int *p, int N)//сортирует по убыванию,N-размер массива
{
    int i, j, max, x;
    for(i = 0; i < N - 1; ++i){
        max = i;
        for(j = i + 1; j < N; ++j){
        if(p[j] > p[max])
            max = j;
        }
        if(max != i){
            x = p[i]; p[i] = p[max];
            p[max] = x;
        }
    }
}
int binary_search(int *p, int R, int Z)//бинарный поиск,возвращает индекс элемента,на место
{ //которого нужно вставить введенный с клавиатуры элемент,R-размер массива,Z-введенное число
    --R;
    int L = 0, mid;
    while(L < R){
        mid = (L + R) / 2;
        if(p[mid] == Z){
            break;
        }
        else{
            if((p[mid] < Z))
                R = mid - 1;
            else
                L = mid + 1;
        }
        if(R - L <= 8){
            while(p[R] < Z)
                --R;
            mid = R + 1;
            break;
        }
    }
    return mid;
}
int main()
{
    int i, j, bs, N, Z, *p;
    puts("Input array size:");
    if(!scanf("%d", &N)){
        fprintf(stderr,"%s\n", "Incorrect input!");
        exit(1);
    }
    p = malloc((N + 1) * sizeof p);
    if(p == NULL){
        fprintf(stderr,"%s\n", "Memory allocation error!");
        exit(2);}
    for(i = 0; i < N; ++i)
        printf("%d ", p[i] = rand() % 1000);
    printf("\n");
    Sort_on_decrease(p, N);
    for(i = 0; i < N; ++i)
        printf("%d ", p[i]);
    printf("\n");
    puts("Input number Z:");
    if(!scanf("%d", &Z)){
        fprintf(stderr,"%s\n", "Incorrect input!");
        exit(3);
    }
    bs = binary_search(p, N, Z);
    for(i = N + 1, j = N; j >= bs; --i, --j)
        p[i] = p[j];
    p[bs] = Z;
    for(i = 0; i < N + 1; ++i)
        printf("%d ", p[i]);
    free(p);
    return 0;
}