#include <cstdlib>
#include <iostream>

using namespace std;

const int sz = 1000000;

int arr[sz];
int temp[sz];

void mergeParts(int *arr, int l, int mid, int r) {
    int i = l, j = mid + 1;
    int k = 0;

    while (i <= mid && j <= r) {
        int nextValue;

        if (arr[i] < arr[j]) nextValue = arr[i++];
        else nextValue = arr[j++];

        temp[k++] = nextValue;
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];

    for (int i=0; i<k; i++) arr[l + i] = temp[i];

}

void mergeSort(int *arr, int l, int r) {
    if (l >= r) return;

    int mid = (l + r) / 2;

    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    mergeParts(arr, l, mid, r);
}


bool check() {
    for (int i=0; i<sz-1; i++){
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

int main(){
    for (int i=0; i<sz; i++) {
        arr[i] = rand() % sz;
    }

    mergeSort(arr, 0, sz - 1);

    cout<<(check() ? "OK": "FAIL");

    return 0;
}