For the first subtask, check each subarray. You can find the longest block of only Ts or only Fs in a subarray in ~\mathcal{O}(N)~. There are ~\mathcal{O}(N^2)~ subarrays, so the final time complexity is ~\mathcal{O}(N^3)~.

Time Complexity: ~\mathcal{O}(N^3)~

For the second subtask, when considering subarrays, categorize them by their left endpoint. Then you can find the longest block of only Ts or only Fs in each of the subarrays with a certain left endpoint in ~\mathcal{O}(N)~.

Time Complexity: ~\mathcal{O}(N^2)~

The third subtask was meant to reward any badly done ~\mathcal{O}(N)~ solutions or potential ~\mathcal{O}(N\sqrt{N})~ or ~\mathcal{O}(N\log N)~ solutions. There is no intended solution.

There are several solutions to the final subtask. The solution discussed below is difficult to come up with, but has a simple implementation.

All indices are ~1~-indexed. Let ~\text{length}(i)~ be the length of the block of only Ts or only Fs which the element at index ~i~ is part of. These values can be computed in ~\mathcal{O}(N)~.

Now consider any odd-length subarray. Observe that if this subarray is suspicious, then the middle element must be part of the subarray's longest block of only Ts or Fs. We will count the number of odd-length subarrays given its middle element. From the previous observation, it can be seen that the number of odd-length subarrays with middle element at index ~i~ is ~\min(\text{length}(i), i, n-i+1)~.

The reasoning for even-length subarrays is similar. If the ~i^\text{th}~ and ~i+1^\text{th}~ answers are both T or both F, there are ~\min (\text{length}(i), i, n-i)~ even-length subarrays whose two middle elements are at index ~i~ and ~i+1~. If the ~i^\text{th}~ answer differs from the ~i+1^\text{th}~ answer, then there are ~\min(\max(\text{length}(i), \text{length}(i+1)), i, n-i)~ even-length subarrays.

Time Complexity: ~\mathcal{O}(N)~