It can be noted that knights of the two players in the duel are the only attackers — when one knight of the two is dead, the dead knight's owner will lose. Therefore the problem itself if more than a matter focusing on which player has the lowest hitpoint — of course the ultimate goal is to execute a player, but if one's knight has a lower hitpoint than the player himself, the another player can opt to instruct the knight to attack his enemy's knight at first.

Hence, the problem is just to make comparisons between $$$\min(a,c)$$$ and $$$\min(b,d)$$$.

• If $$$\min(a, c) \gt \min(b, d)$$$, Gellyfish will win.
• If $$$\min(a, c)=\min(b, d)$$$, Gellyfish will win because he attacks first.
• If $$$\min(a, c) \lt \min(b, d)$$$, Flower will win.

In other words, if and only if $$$\min(a, c) \lt \min(b, d)$$$ can Flower win.

void solve()
{
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    std::cout << (std::min(a, c) < std::min(b, d) ? "Flower" : "Gellyfish") << std::endl;
}

It can be discovered that $$$2^a$$$ is far more than $$$2^b$$$ if $$$a \gt b$$$. Therefore, we should make at least one of the two integers $$$p_j$$$ and $$$q_{i-j}$$$ to make the sum of them to the maximum.

Suppose $$$M_i=\max\big(\max(p[0..i]),\max(q[0..i])\big)$$$. It can be proved that $$$\forall j,k\in [0,i], p_j\le M_i, q_k\le M_i$$$. Then we have

and that the maximum $$$r_i$$$ should be from a pair $$$(p_j,q_{i-j})$$$ with at least one element equal to $$$M_i$$$ — the sum of elements in the pair should be no more than $$$2^{M_i-1}+2^{M_i-1}=2^{M_i}$$$ otherwise, but $$$\forall m\ge 0, 2^{M_i} \lt 2^{M_i}+1\le 2^{M_i}+2^m$$$.

Now the problem has returned to the matter of finding the best pair $$$(p_j,q_{i-j})$$$ where there is at least $$$1$$$ $$$M_i$$$ for each $$$i$$$.

• If $$$\max(p[0..i])=M_i$$$, suppose that $$$M_i$$$ occurs at $$$p_x$$$ — the pair now turns out to be $$$(p_x, q_{i-x})$$$.
• If $$$\max(q[0..i])=M_i$$$, suppose that $$$M_i$$$ occurs at $$$q_y$$$ — the pair now turns out to be $$$(p_{i-y}, q_y)$$$.

The element other than $$$M_i$$$, marked as $$$m_i$$$, should be equal to $$$\max(p_{i-x},q_{i-y})$$$. $$$r_i=2^{M_i}+2^{m_i}$$$, under this circumstance, should reach its maximum.

Read before:

If you know how to calculate exponentiation with a very low time complexity, skip this section.

Suppose we are to calculate out the value of $$$a^b$$$. We can convert the exponent to a binary form to split a complex task into pieces. For example, suppose $$$b=(\overline{b_{n-1}\dots b_1b_0})_2$$$, there should be

therefore

Having taken all above into account, we can reach a recursion by moving digits of the binary-styled exponential right one-by-one to get the answer of $$$a^b$$$.

const int recommendedMod = 998244353;

/**
 * @brief Fast Power. If a great number modulo is asked for a fraction x/y, use `((fastPow(y, mod - 2, mod) % mod) * (x % mod)) % mod`.
 *
 * @param base The base.
 * @param power The power.
 * @param mod The mod.
 * @return ll The answer of (base ^ power) % mod (here ^ means exponential calculation)
 */
ll fastPow(ll base, ll power, ll mod = recommendedMod)
{
    ll result = 1 % mod;
    while (power > 0)
    {
        if (power & 1)
            result = result * base % mod;
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> p(n), q(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> p[i];
    }
    for (int i = 0; i < n; i++)
    {
        std::cin >> q[i];
    }
    int maxPIndex = 0, maxQIndex = 0;
    int maxP = INT_MIN, maxQ = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        if (p[i] > maxP)
        {
            maxP = p[i];
            maxPIndex = i;
        }
        if (q[i] > maxQ)
        {
            maxQ = q[i];
            maxQIndex = i;
        }
        int maxOfAll = std::max(maxP, maxQ), otherElem;
        if (maxP == maxQ)
            otherElem = std::max(q[i - maxPIndex], p[i - maxQIndex]);
        else
            otherElem = maxOfAll == maxP ? q[i - maxPIndex] : p[i - maxQIndex];
        std::cout << (fastPow(2, otherElem) + fastPow(2, maxOfAll)) % recommendedMod << " ";
    }
    std::cout << std::endl;
}

Theories have it that

Therefore, the value $$$g$$$ which all elements in the array finally equal to is the greatest common divisor of all initial elements in the array. So just count the number of elements having been equal to the GCD already (marked as $$$x$$$) —

• If $$$x \gt 0$$$, there has been at least $$$1$$$ element that equals to $$$g$$$. For other elements, make and only make $$$1$$$ operation with the equal-to-$$$g$$$ element to reach $$$g$$$. The corresponding number of operations will be $$$n-x$$$.
• If $$$x=0$$$, there is no element that equals to $$$g$$$ in the array above all. We can use Breadth First Search (or BFS) algorithm to find the minimum subset of length $$$m$$$ of which the GCD is $$$g$$$ in steps shown below. Then we can get $$$g$$$ in $$$m-1$$$ steps, and for the remaining $$$n-1$$$ elements we only need $$$1$$$ single operation to make them $$$g$$$. The corresponding total number of operations will be $$$(m-1)+(n-1)=m+n-2$$$.
• • Divide all elements by $$$g$$$ (we have got it at first) to get the new array. Our task has afterwards turned into searching for a minimum subset of length $$$m$$$ of which the GCD is $$$1$$$.
• • Employ BFS — select an element of all, from which we extend for subset one by one and calculate the current GCD. Once the subset's GCD has turned $$$1$$$, we note down the current size of the subset which we compare with the current minimum size of all subsets.
• • The ultimate minimum size of the subset $$$m$$$ can be reached. We can conduct a $$$\text{gcd}$$$ operation for a pair of two elements that can reach $$$g$$$ first and make the remaining $$$m-1$$$ elements $$$g$$$ by $$$\text{gcd}(\text{randomElement},g)$$$.

In other words, the answer should be

long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> a[i];
    }

    if (n == 0)
    {
        std::cout << 0 << std::endl;
        return;
    }

    long long g_val = a[0];
    for (int i = 1; i < n; i++)
    {
        g_val = gcd(g_val, a[i]);
    }

    int count = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == g_val)
        {
            count++;
        }
    }

    if (count >= 1)
    {
        std::cout << (n - count) << std::endl;
        return;
    }
    std::set<long long> distinct;
    for (int i = 0; i < n; i++)
    {
        distinct.insert(a[i] / g_val);
    }

    std::map<long long, int> best_state;
    std::queue<std::pair<long long, int>> state_queue;
    int min_set_size = INT_MAX;

    for (long long d : distinct)
    {
        best_state[d] = 1;
        state_queue.push({d, 1});
    }

    while (!state_queue.empty())
    {
        auto [current_g, current_size] = state_queue.front();
        state_queue.pop();

        if (best_state[current_g] < current_size)
        {
            continue;
        }

        if (current_g == 1)
        {
            min_set_size = std::min(min_set_size, current_size);
        }

        if (min_set_size != INT_MAX && current_size >= min_set_size)
        {
            continue;
        }

        if (current_size >= 7)
        {
            continue;
        }

        for (long long d : distinct)
        {
            long long new_g = gcd(current_g, d);
            int new_size = current_size + 1;

            if (min_set_size != INT_MAX && new_size >= min_set_size && new_g != 1)
            {
                continue;
            }

            auto it = best_state.find(new_g);
            if (it == best_state.end() || it->second > new_size)
            {
                best_state[new_g] = new_size;
                if (new_g == 1)
                {
                    min_set_size = std::min(min_set_size, new_size);
                }
                else
                {
                    if (new_size < 7)
                    {
                        state_queue.push({new_g, new_size});
                    }
                }
            }
        }
    }

    if (min_set_size == INT_MAX)
    {
        min_set_size = 7;
    }
    std::cout << (n + min_set_size - 2) << std::endl;
}