#include <stdio.h>

// Modified binary search: find first occurrence or insertion index
int binarySearch(int arr[], int n, int target) {
        int low = 0, high = n - 1, result = n;
            while (low <= high) {
                        int mid = (low + high) / 2;
                                if (arr[mid] == target) {
                                                result = mid;
                                                            high = mid - 1; // search left for first occurrence
                                } else if (arr[mid] < target) {
                                                low = mid + 1;
                                } else {
                                                result = mid; // potential insert index
                                                            high = mid - 1;
                                }
            }
                return result;
}

int main() {
        int n, target;
            printf("Enter number of books (n): "books (n): ");
                scanf("%d", &n);
                
                    if (n < 0) {
                                printf("Invalid input\n");
                                        return 0;
                                            }
                                            
                                                int arr[100]; // assuming max 100 books
                                                    //printf("Enter sorted book IDs: ");
                                                        for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
                                                        
                                                            // Basic sorted check (optional)
                                                                for (int i = 1; i < n; i++) {
                                                                            if (arr[i] < arr[i - 1]) {
                                                                                            printf("Invalid input\n");
                                                                                                        return 0;
                                                                                                                }
                                                                                                                    }
                                                                                                                    
                                                                                                                        
                                                                                                                            scanf("%d", &target);
                                                                                                                            
                                                                                                                                int index = binarySearch(arr, n, target);
                                                                                                                                    if (index < n && arr[index] == target) {
                                                                                                                                                printf("%d\n", index);
                                                                                                                                                    } else {
                                                                                                                                                                printf(" %d\n", index);
                                                                                                                                                                    }
                                                                                                                                                                    
                                                                                                                                                                        return 0;
                                                                                                                                                                        
                                                                                                                                                                        
}