Given a pair of starting intersections ~E~ and ~S~, with ~M = \frac{E+S}{2}~, let ~K~ be the number of intersections which each car will visit (~K = M-S+1~). Let ~X_{1 \dots K}~ be the times at which Ethan would arrive at each of the intersections on his path (such that ~X_1 = 0~, ~X_2 = T_S~, ~X_3 = T_S+T_{S+1}~, and so on). Similarly, let ~Y_{1 \dots K}~ be Solomon's sequence of arrival times. Then, let ~D_{1 \dots K}~ be a sequence of differences between these arrival times (such that ~D_i = X_i-Y_i~). If we were to remove all ~0~'s from ~D_{1 \dots K}~, then the CCCC would be equal to the number of elements in ~D~ which either have no preceding element, or have a different sign than their preceding element. If we consider each ~(E, S)~ pair independently, computing its ~D~ sequence and resulting CCCC value in this fashion would take ~\mathcal O(K)~ time, which would result in an ~\mathcal O(N^3)~ algorithm overall. We'll need to do better than that to obtain full marks.

Let's consider each possible bomb intersection ~M~, and let's imagine for the moment that Ethan and Solomon are each driving away from it rather than towards it. We'll define a similar set of sequences to the ones described above. Let ~X'_i~ be the time at which Ethan would arrive at the ~i~-th intersection when driving left from ~M~ (such that ~X'_1 = 0~, ~X'_2 = T_M~, ~X'_3 = T_M+T_{M-1}~, and so on). Similarly, let ~Y'_i~ be the time at which Solomon would arrive at the ~i~-th intersection when driving right from ~M~, and let ~D'_i = X'_i-Y'_i~. We can now make the key insight that, for any ~K~, ~D_{1 \dots K}~ is similar to ~D'_{1 \dots K}~ — just reversed (which is irrelevant), and shifted by subtracting ~D'_K~ from each of its values (such that ~D_1~ ends up being equal to ~0~).

One way of thinking about the CCCC of a given sequence ~D_{1 \dots K}~ is that it's equal to the number of times that it "crosses" ~0~ (the number of times which there's a positive value followed by zero or more ~0~'s followed by a negative value, or vice versa), plus ~1~ if the sequence has at least ~1~ non-zero value. And by the same token, the CCCC of a given sequence ~D'_{1 \dots K}~ is then the number of times that it "crosses" ~D'_K~. For example:

• The CCCC of ~D' = [3, 3, 3]~ is ~0~ (as its values are all equal to ~3~)
• The CCCC of ~D' = [1, 3, 2]~ is ~2~ (as ~2~ is crossed by ~1 \to 3~, and not all of its values are equal to ~2~)
• The CCCC of ~D' = [1, 2, 2, 3, 2]~ is ~2~ (as ~2~ is crossed by ~1 \to 2 \to 2 \to 3~, and not all of its values are equal to ~2~)
• The CCCC of ~D' = [1, 2, 2, 1, 2]~ is ~1~ (as not all of its values are equal to ~2~)

We can represent a ~D'~ sequence as a set of intervals of crossed values, based on pairs of adjacent elements. For example, if ~D' = [5, 10, 10, 15, 12]~, then all values in the exclusive intervals ~(5, 10)~, ~(10, 10)~, ~(10, 15)~, and ~(12, 15)~ are crossed (in other words, in the inclusive intervals ~[6, 9]~, ~[11, 14]~, and ~[13, 14]~). Furthermore, if we exclude intervals with both endpoints equal (of the form ~(x, x)~), then if two intervals in a row go in the same direction (either both are increasing or both are decreasing), then their joining value is also crossed. In this example, ~5 \to 10~ and ~10 \to 15~ satisfy this property, meaning that ~10~ is also crossed. However, ~10 \to 15~ and ~15 \to 12~ don't, meaning that ~15~ is not crossed.

With this representation, we're ready to compute all of the CCCCs for a given bomb intersection ~M~ efficiently. We'll start by iterating outwards from it in both directions to compute its full ~D'~ sequence in ~\mathcal O(N)~ time. We'll then compress the original values in ~D'~ down to values ~1 \dots C~, where ~C~ is the number of distinct values in ~D'~ (such that ~C~ is in ~\mathcal O(N)~), in ~\mathcal O(N \log N)~ time. We'll proceed to iterate ~i~ upwards from ~1~ to ~|D'|~ while maintaining information about intervals of crossed values — specifically, we'll use a binary indexed tree to maintain an array ~A~ in which ~A_x~ is the difference between the number of intervals starting at and ending at ~x~ (such that the sum of ~A_{1 \dots x}~ is then the number of intervals spanning ~x~). For each ~i~, we'll query for the number of intervals so far which encompass ~D'_i~ in order to compute the CCCC of ~D'_{1 \dots i}~ (in other words, the CCCC of the ~(S, E)~ pair ~(M-(i-1), M+(i-1))~), and we'll then insert at most ~2~ intervals based on ~D'_i~. In total, this process takes ~\mathcal O(N \log N)~ time per bomb intersection ~M~, resulting in an overall time complexity of ~\mathcal O(N^2 \log N)~.