For starters, we need to be able to compare a pair of public keys and determine which one is weaker. This can be done by prime factorizing each one to compute its private key, and then comparing the private keys by the earliest index at which they differ. The process can be simplified and sped up in the average case by prime factorizing both values simultaneously, stopping as soon one of their private keys has been found to be lexicographically smaller than the other, though this is not necessary.

Prime factorizing a single integer ~x~ is a standard procedure which can be accomplished in ~\mathcal O(\sqrt x)~ time by looping a variable ~p~ up from ~2~ to ~\sqrt x~. At each iteration, if ~x~ is divisible by ~p~, then ~p~ must be a prime factor of ~x~, at which point we can repeatedly divide ~x~ by ~p~ as long as it's still divisible by it in order to determine ~p~'s exponent in the factorization. Once ~p~ has exceeded ~\sqrt x~, if the final value of ~x~ is still larger than ~1~, it must be a prime factor itself (with an exponent of ~1~).

A naive solution consists of testing if each computer is a valid weakpoint, until one is found. In the worst case, this requires comparing every pair of adjacent computers, which requires prime factorizing all ~N~ public keys at least once. As such, the time complexity is ~\mathcal O(N \sqrt K)~, where ~K~ is the largest ~A_i~ value of any computer. Since ~N \le 100\,000~ and ~K \le 10^9~ (so ~\sqrt K~ is roughly less than ~32\,000~), the worst-case number of steps taken will be ~100\,000 \times 32\,000 = 3.2~ billion, which is too slow. The ~\sqrt K~ factor can be optimized through advanced prime factorization techniques such as the Sieve of Eratosthenes, Fermat's method, or Pollard's rho algorithm. However, these techniques can be dubious to depend on during a live contest. To achieve a better time complexity, we can instead try to optimize the ~N~ factor – in other words, find a way to somehow not have to prime factorize every public key.

We can formulate this problem in another way. If we let ~F(i)~ be the private key of the ~i~-th computer, then we're looking for any local minimum of the function ~F~. Despite the fact that ~F~ is only defined at integer values, we can use a technique common for finding local minima of continuous curves – namely, ternary search. At all points in the ternary search, we'll maintain the invariant that at least one local minimum must exist in the range of indices ~a \dots b~. Initially, ~a = 1~ and ~b = N~, and we'll stop once ~a = b~. Let's now compare the values of the function ~F~ one-third and two-thirds between ~a~ and ~b~ – specifically, if we let ~x = \lfloor \frac{a+a+b}{3} \rfloor~ and ~y = \lceil \frac{a+b+b}{3} \rceil = \lfloor \frac{a+b+b+2}{3} \rfloor~, we want to compare ~F(x)~ to ~F(y)~ (~x~ is rounded down while ~y~ is rounded up so that, when ~b = a+1~, we'll have ~x = a~ and ~y = b~). Now, if ~F(x) < F(y)~, then there must be at least one local minimum in the range of indices ~a \dots (y-1)~, so we can set ~b = y-1~. Otherwise, if ~F(x) > F(y)~, we can set ~a = x+1~. At each iteration of this ternary search, the size of the range ~a \dots b~ reduces by approximately ~\frac 1 3~, meaning that it will be reduced to size one after ~\mathcal O(\log_3 N)~ iterations. Therefore, the time complexity of this algorithm is ~\mathcal O(\log N \times \sqrt K)~, which is sufficient to pass.

The ternary search can also be replaced with a very similar binary search. Consider a range of the array ~A[a \dots b]~. First, we can check to make sure that neither ~a~ nor ~b~ (the endpoints) are weakpoints. If even one of them is a weakpoint, then we are done. Otherwise, we can find the midpoint ~m = \frac{a+b}{2}~ to break the interval in half. There are two cases:

1. ~F(m) < F(m+1)~: \.../.../ - in which we should recursively examine the left subinterval ~[a, m]~
2. ~F(m) > F(m+1)~: \...\.../ - in which we should recursively examine the right subinterval ~[m+1, b]~

Eventually, we must have found a local minimum when the length of the interval is reduced to ~1~. In fact, a careful implementation will render it unnecessary to check the endpoints. The time complexity of this algorithm is also ~\mathcal O(\log N \times \sqrt K)~, which is faster than the previous ternary search solution by only a constant factor.