We split the solution into three parts.

1. Finding a lower bound on the number of operations.
2. Showing that the lower bound is attainable by providing a solution with that number of operations and at most $N$ runs.
3. Deriving $f(N)$ and showing how to modify the solution above to receive full credit.

Part 1: the lower bound

Let $a_i$ be the number of times we attack enemy $i$. We must have $0\le a_i\le v_i$ ($i$-th constraint of type 1) and $a_{i-1}+a_i+a_{i+1}\ge v_i$ ($i$-th constraint of type 2), and want to minimize $\sum a_i$. There are also additional constraints that the $a_i$ must satisfy in order to be possible, but let's ignore them for now.

Let's start with all $a_i$ equal to zero and then try to satisfy the constraints of type 2 greedily from left to right by choosing some $a_i$ to increase. Specifically, in order to satisfy the $i$-th constraint of type 2, we should first try to increase $a_{i+1}$ as much as possible (which can help satisfy the most constraints of type 2 that haven't been satisfied yet), and increase $a_i$ only if we're forced to.

This gives a lower bound on $\sum a_i$, and in part 2 we can prove it is attainable.

Part 2: a construction

Let's output a construction with exactly one run for each nonzero $a_i$ from part 1. There are several different ways to do this, and here we describe only one such way.

The thing is that for indices $i$ with $a_i>0$ and $a_{i-1}+a_i+a_{i+1}>v_i$ (sensitive indices), we have to be careful about when we perform the operations on $i$, because it is definitely not allowed to leave them for last. In fact, we can prove that there are no two adjacent sensitive indices, so we can just first perform operations on all sensitive indices, then on all remaining indices.

This claim can be proven via casework. More for each index $i$, write an R at it if $a_{i+1}$ increases to satisfy the $i$-th type 2 constraint, and an S at it if $a_i$ increases to satisfy the $i$-th type 2 constraint (possibly both). We can note that:

• If an index has an S, then the subsequent index has no letters written at it.
• From the previous observation, no two Ss are at adjacent indices.
• An index can be sensitive only if an adjacent index has a S.
• If we have Ss at both indices $i$ and $i+3$, then $a_{i+2}=0$ since there is no R at $i+1$ and no S at $i+2$. so we can't have both $i+1$ and $i+2$ being sensitive

There are other orderings of runs that work due to similar reasoning. For example, performing the operations from largest index to smallest index, and swapping the order of some disjoint adjacent pairs as necessary.

Side note: If there is a construction with a given $a$, then there is a construction with each nonzero $a_i$ contributing exactly one run. This is because given any construction, the construction remains valid when every operation on index $i$ is moved to be adjacent to the last operation on index $i$. If $v_i>0$ just before the last operation on $i$ in the original construction is performed, then this also holds in the modified construction.

Part 3: a small modification

We claim that $f(N)=N$ when $N$ is odd. Indeed, consider $v=[3,1,3,1,\dots,1,3]$ (alternating big and small). We should always operate on all the small values because that's the only way to reduce two big values at the same time with one operation. Additionally, we'll need to operate on all big values at least once to reduce them to zero. So the construction from part 2 already works for odd $N$.

When $N$ is even, $f(N)=f(N-1)=N-1$, but our solution might output a construction with $N$ runs when $v_1>v_2<v_3>v_4<\dots >v_N$. In this case, we can just reverse the input array before constructing the solution, since it is impossible for both the input and its reverse to be in this order.

#include <bits/stdc++.h>
using namespace std;

template <class T> using V = vector<T>;
#define all(x) begin(x), end(x)

using ll = long long;

int M;

pair<ll, vector<pair<int, ll>>> get_ops(const vector<ll> &v) {
    int N = size(v);

    // get op count
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {  // satisfy i-th type 2 constraint by increasing a_{i+1} and a_i
        ll remaining = v.at(i) - a.at(i);
        if (i > 0) remaining -= a.at(i - 1);
        remaining = max(remaining, 0LL);
        if (i + 1 < N) {
            a.at(i + 1) = min(remaining, v.at(i + 1));
            remaining -= a.at(i + 1);
        }
        a.at(i) += remaining;
    }
    ll op_count = accumulate(begin(a), end(a), 0LL);

    // construction
    auto sensitive = [&](int i) {
        assert(0 <= i && i < N);
        return ((i == 0 ? 0 : a.at(i - 1)) + a.at(i) +
                    (i + 1 == N ? 0 : a.at(i + 1)) >
                v.at(i)) &&
               a.at(i);
    };
    vector<pair<int, ll>> runs;
    for (int i = 0; i < N; ++i)
        if (sensitive(i)) {
            if (i) assert(!sensitive(i - 1));
            // sanity check: no two consecutive sensitive indices
            runs.push_back({i, a.at(i)});
        }
    for (int i = 0; i < N; ++i)
        if (!sensitive(i) && a.at(i)) { runs.push_back({i, a.at(i)}); }
    return {op_count, runs};
}

void solve() {
    int N;
    cin >> N;
    vector<ll> v(N);
    for (auto &t : v) cin >> t;
    auto ans = get_ops(v);
    bool rev = false;
    if (N % 2 == 0 && size(ans.second) == N) {  // for M=2
        rev = true;
        reverse(all(v));
        ans = get_ops(v);
        assert(size(ans.second) < N);
    }
    const auto &[op_count, runs] = ans;
    cout << op_count << "\n";
    if (M) {
        cout << size(runs) << "\n";
        for (auto [i, r] : runs)
            cout << (rev ? N - i : i + 1) << " " << r << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T >> M;
    while (T--) solve();
}