#include <stdio.h>

int main() {
    int frames, pages, i, j, page_faults = 0, flag = 0, pos = 0;
    
    printf("Enter the number of frames: ");
    scanf("%d", &frames);
    
    printf("Enter the number of pages: ");
    scanf("%d", &pages);
    
    int frame[frames], page[pages];
    int temp[frames];
    
    for (i = 0; i < frames; i++) {
        frame[i] = -1;
    }
    
    printf("Enter reference string: ");
    for (i = 0; i < pages; i++) {
        scanf("%d", &page[i]);
    }
    
    for (i = 0; i < pages; i++) {
        flag = 0;
        for (j = 0; j < frames; j++) {
            if (frame[j] == page[i]) {
                flag = 1;
                break;
            }
        }
        
        if (flag == 0) {
            if (pos < frames) {
                frame[pos++] = page[i];
            } else {
                int farthest = 0;
                for (j = 0; j < frames; j++) {
                    temp[j] = -1;
                    for (int k = i + 1; k < pages; k++) {
                        if (frame[j] == page[k]) {
                            temp[j] = k;
                            break;
                        }
                    }
                    if (temp[j] == -1) {
                        farthest = j;
                        break;
                    } else {
                        if (temp[j] > temp[farthest] || (temp[j] == temp[farthest] && j < farthest)) {
                            farthest = j;
                        }
                    }
                }
                frame[farthest] = page[i];
                page_faults++;
            }
        }
    }
    
    printf("Total Page Faults: %d\n", page_faults);
    
    return 0;
}