Company: Myntra
Difficulty: medium
Destroy All Monsters N monsters stand in a row. The power of the i -th of them is A[i] . N is even. You clear the row by repeatedly making two monsters clash. In one clash you pick two different monsters from the three positions of the row as it currently stands — its start , its middle and its end — and they destroy each other. The energy you spend on that clash equals gcd of their two powers. Both monsters leave the row; the survivors keep their relative order and immediately form the new row, whose start, middle and end are then read afresh. Because N is even and every clash removes two monsters, the row always has even length. The middle of a row of length L is the element at index L / 2 using 0-based indexing — the second of the two central elements. (When L = 2 the middle and the end are the same monster, so the only possible clash is start against end.) Report the minimum total energy needed to destroy all N monsters. Input Format The first line contains the integer N . The seco