Note that $$$N$$$ has to be read as a signed 64-bit integer type. You could check it by either doing to comparison manually, or casting back and forth between the signed 32-bit integer type.

Time complexity: $$$O(1)$$$

Simply construct a $$$W$$$-by-$$$H$$$ matrix, assign $$$B_{i, j} = A_{j, i}$$$ for all relevant $$$i, j$$$, then output it.

Alternatively, if you use Python, the numpy library installed in AtCoder gives a really short implementation, as noted in this user editorial: https://atcoder.jp/contests/abc237/editorial/3344

Time complexity: $$$O(HW)$$$

Note that for a string to be a palindrome, it must start with the same number of contiguous as as it ends with.

If there are less contiguous as at the end of $$$S$$$ than at is start, the answer is No. Otherwise, add the difference in number of as to its start, then test if it is a palindrome.

Time complexity: $$$O(|S|)$$$

There are at least two methods that could be used, a straightforward method with linked list, or a reversed method with deque.

The straightforward method with linked list:

One could make a simple linked list using two arrays, $$$pr$$$ "previous" and $$$nx$$$ "next", where $$$pr[i]$$$ is the index of the node before $$$i$$$ in the list, while $$$nx[i]$$$ is the index of the node after $$$i$$$ in the list. One node ($$$N+1$$$ is convenient for this problem, thus making $$$N+2$$$ total nodes) is reserved as the "sentinel" node, whose $$$nx[s]$$$ points to the first element, and $$$pr[s]$$$ points to the last element of the list.

Then implement as in the problem statement. For the L case you should insert the new node between $$$pr[i]$$$ and $$$i$$$ by updating the $$$pr$$$ and $$$nx$$$ arrays, for the R case, insert the new node between $$$i$$$ and $$$nx[i]$$$.

Reversed method with deque:

Consider the operations in reversed order.

L is equivalent to appending $$$i-1$$$ to the right of $$$A$$$, as $$$i$$$ is already in $$$A$$$, and everything in between was supposed to be added after $$$i$$$ in the normal order. Similarly, R is equivalent to appending $$$i-1$$$ to the left of $$$A$$$.

To efficiently perform these operations, we use a deque, that allow amortized $$$O(1)$$$ appending to either end of the logical array.

Time complexity: $$$O(N)$$$

Construct the weighted directed graph and run Dijkstra's algorithm from each node. However we have to deal with the fact that the goal node is the same as the source node. There are several ways:

• Set the cost of the source node to $$$\infty$$$ and prepopulate the priority queue with the nodes directly reachable from the source
• Create a new fictional node $$$n+1$$$ to use as the goal node. Redirect all back-to-source edges there.
• First precalculate the cheapest edge from each node to the source node (or $$$\infty$$$ if there are none). Run Dijkstra as normal, then add the costs and find the minimum.

Time complexity: $$$O(N (N+M) \log (N+M))$$$

Observe that a value $$$x$$$ could be the final value iff $$$x \leq \min A$$$ AND $$$x$$$ is the gcd of some non-empty subset of $$$A$$$.

For the latter condition to hold, $$$x$$$ must be a divisor of at least one value $$$A_i$$$. Also, if $$$[A_a, A_b, ..., A_c]$$$ are all the values of $$$A$$$ divisible by $$$x$$$, their collective gcd must be equal to $$$x$$$.

Thus we can iterate through the divisors of each $$$A_i$$$ and maintain a hashmap, mapping a divisor to the collective gcd of its multiples in $$$A$$$, then count the number of divisors that satisfy.

Time complexity: $$$O(N (\sqrt M + D \log M))$$$, where $$$M = \max A$$$ and $$$D$$$ is the maximum number of divisors for a value $$$A_i$$$, which can be considered roughly $$$O(M^{1/3})$$$.