Ciao, il problema è nell'acquisizione dell'array:
for (i=1; i<=n; i++){
printf("\nInserisci il %d valore: ",i);
scanf("%d",&array[i]);
}
In particolare gli indici degli array iniziano da zero, non da uno. Per cui questo codice lascia "vuota" la prima cella (che, in realtà, sarà popolata da un valore casuale), e "sborda" di uno, cioè inserisce l'ultimo elemento nella cella di memoria immediatamente
fuori dall'array, cosa che potrebbe causarti fra l'altro un segmentation fault.
Di conseguenza ti basta sistemare quel codice e dovrebbe funzionare tutto.