Solve the Secretary Problem The Secretary Problem is a famous problem described as thus:

You need a new secretary
You have N applicants that you can interview one at a time
You are able to score each applicant after the interview.  Your scoring system will never give two applicants the same score
After you interview an applicant, you must give an immediate &quot;yes&quot; or &quot;no&quot;
You want the applicant with the highest score

The solution is to interview the first floor(N/e) applicants, and then accept the first applicant that has a higher score than all of the previous applicants.   If none of the applicants are higher, then return the last applicant.  Interestingly enough, this gives the top applicant 1/e percent of the time.  e refers to Euler's number.  To get the value of e, you can use a builtin, log, or hardcode it to at least 5 decimal points.
Input:
An non-empty array of unique non-negative integers no more than 2^31-1.
Output:
An integer representing the chosen candidate.  To be clear the algorithm is:

Find the maximum element in the first floor(N/e) elements of the array.
Iterate through the remaining elements, and return the first element that is higher than the maximum found on step 1.
If none of the elements are higher, than return the last element.

For example, say your array was [2,7,4,3,9,20], so N = 6 and floor(N/e) = 2.  The first 2 elements of the array is [2,7].  The max of [2,7] is 7.  The remaining elements are [4,3,9,20].  The first element that is greater than 7 is 9, so we return 9.
Test Cases:
[0]         =&gt; 0
[100]       =&gt; 100
[100, 45]   =&gt; 100
[0, 1]      =&gt; 0
[45, 100]   =&gt; 45
[1, 4, 5]   =&gt; 4
[1, 5, 4]   =&gt; 5
[5, 4, 1]   =&gt; 1
[5, 1, 4]   =&gt; 4
[4, 1, 5]   =&gt; 5
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
=&gt; 98
[10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30]
=&gt; 30

Your solution must be O(n), where n is the length of the array.  If your language has a builtin that finds the maximum of an array, you can assume that the function takes O(n) (and hopefully it does).
Standard loopholes apply, and this is a code-golf, so the make the shortest answer in your favorite language!
Jelly, 13 bytes

L:Øe³ḣȯ-Ṁ&lt;i1ị


Definitely an O(n) algorithm, hopefully an O(n) implementation. Try it online!

How it works

L:Øe³ḣȯ-Ṁ&lt;i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         &lt;     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).