The first subtask is solvable with brute force, by trying out each possible interval. There are ~\mathcal O(n^2)~ such intervals, and by naively calculating the sum in ~\mathcal O(n)~ and the greatest common divisor in ~\mathcal O(n \ln MAX)~, where ~MAX~ is the largest height of a skyscraper, it is possible to achieve a complexity of ~\mathcal O(n^3 \ln MAX)~ which is enough to solve this subtask.

Let the function ~S(l, r) := h_l+h_{l+1}+\dots+h_r~ be the sum of heights of all skyscrapers inside an interval, and let ~\gcd(l, r) := G(h_l, h_{l+1}, \dots, h_r)~ be their greatest common divisor. Notice that the beauty of an interval ~[l, r]~ is exactly ~S(l, r) \cdot G(l, r)~. For the solution of the second subtask, notice the following relations: ~S(l, r) = S(l, r-1)+h_r~ and ~G(l, r) = \gcd(G(l, r-1), h_r)~. By that relation, it is possible to calculate all values of the functions ~S~ and ~G~ in complexities ~\mathcal O(n^2)~ and ~\mathcal O(n^2 \ln MAX)~ respectively. That is enough to solve the second subtask.

For the full solution, you should notice the following. For the function ~S~, the following also holds for ~l > 1~, ~S(l, r) = S(r, 1)-S(l-1, 1)~. It is enough to calculate all values of ~S(1, r)~ in ~\mathcal O(n)~ and that is enough to be able to calculate the value of all ~S(l, r)~ in ~\mathcal O(1)~. Let us now fix the right border ~r~ of the interval we will look at. Notice the following holds for each ~l < r~: ~G(l, r) = G(l+1, r)~, or ~G(l, r) \mid G(l+1, r)~ which implies ~2G(l, r) \le G(l+1, r)~. Now notice that the function ~G(l, r)~ can achieve at most ~\log MAX~ different values for a fixed ~r~.

Now, notice that for a fixed ~l~, ~G(l, r) = G(l+1, r)~ implies ~G(l, r+1) = G(l+1, r+1)~. It follows that it is enough to maintain the leftmost ~l~ which achieves each possible value of ~G~ for the current border ~r~. Because there are at most ~\mathcal O(\log MAX)~ of them, it is possible to iterate through all of them and calculate their beauties. When switching the right border from ~r~ to ~r+1~, it is enough to try and add the border ~r+1~ for the interval ~[r+1, r+1]~, and check for each of the current left borders whether the inequality ~G(l, r) > G(l-1, r)~ still holds for ~G(l, r+1) > G(l-1, r+1)~. This can be done using Euclid's algorithm. This gives us an algorithm of the complexity ~\mathcal O(n \log MAX \ln MAX)~ which is enough for full score. Notice that there exist similar algorithms with the same complexity which have a far worse constant. Such implementations were supposed to get points on the third and fourth subtasks.