At first glance, it may seem that there are ~10^9~ possible values of ~X~ to consider. However, we only need to bother considering at most ~G~ of them, the ones which are equal to ~SG_i~ (for some ~i~), as it can't help Gimli to choose some other arbitrary value of ~X~. This immediately gives us a solution with a time complexity of ~\mathcal O(LG)~, in which we try each such value of ~X~, and tally up Legolas and Gimli's scores for it (by iterating over all of their killed enemies) to determine whether it's valid.

However, the above solution isn't efficient enough to receive full marks. To do better, let's start by sorting the values ~SL_{1 \dots L}~ in non-increasing order (which can be done in ~\mathcal O(L \log L)~ time), and do the same with the values ~SG_{1 \dots G}~ (in ~\mathcal O(G \log G)~ time).

Let's now consider trying each possible value of ~X~ in this order, with the largest ones first. Let's skip indices ~i~ such that ~SG_i = SG_{i+1}~. Now, when we consider ~X = SG_i~, we can determine Gimli's score without iterating over all of his killed enemies – his score is simply ~i~ (as the values ~SG_{1 \dots i}~ are larger than or equal to ~X~ while the values ~SG_{(i+1) \dots G}~ are smaller than it).

Determining Legolas's score is trickier, but we can observe that there must be some corresponding index ~j~ such that the values ~SL_{1 \dots j}~ are larger than or equal to ~X~ while the values ~SL_{(j+1) \dots L}~ are smaller than it, meaning that Legolas's score is ~j~. Furthermore, as ~i~ increases, ~X~ cannot increase and so ~j~ cannot decrease. Therefore, as we iterate over values of ~i~, we can update ~j~ as necessary (incrementing it as long as ~SL_{j+1} \ge X~), and stop if we find a value of ~X~ for which ~i > j~.

The overall time complexity of this algorithm is ~\mathcal O(L \log L)~.