open System

// Array of random numbers with the property that A[1] > A[2] and A[n] > A[n-1]
let A =
    [|
    22; 21; 21; 62; 11
    57; 10; 69; 29; 12
    81; 90; 51; 89; 48
    82; 11; 8; 43; 69
    |]

// Finds a local min in log(n) time
let rec getLocalMin (A:int array) =
    let n = A.Length

    // Stores the first, last, and middle elements of the array
    let first = A.[0]
    let middle = A.[n/2]
    let last = A.[n-1]

    // Stores the elements to the left and right of the middle element
    let left = A.[n/2 - 1]
    let right = A.[n/2 + 1]

    // Is middle a local min?
    match (left >= middle) && (right >= middle) with
    | true -> middle                                                 // If it is a local min, return it
    | false when left <= middle -> getLocalMin (Array.sub A 0 (n/2)) // If the left is smaller, find the local min of elements between 0 and n/2
    | false -> getLocalMin (Array.sub A (n/2) (n-1))                 // If the right is smaller, find the local min of elements between n/2 and n-1

let min = getLocalMin A
printf "%i" min