#include <iostream>
#include <vector>
using namespace std;
struct Node {
long long sum = 0;
long long min_pref = 0;
int min_idx = 0;
};
class SegTree {
public:
explicit SegTree(const vector<long long>& values) : n(static_cast<int>(values.size()) - 1) {
tree.resize(4 * n + 5);
build(1, 1, n, values);
}
void point_update(int index, long long value) {
point_update(1, 1, n, index, value);
}
Node query_all() const {
return tree[1];
}
private:
int n;
vector<Node> tree;
static Node merge(const Node& left, const Node& right) {
Node result;
result.sum = left.sum + right.sum;
const long long right_pref = left.sum + right.min_pref;
if (left.min_pref <= right_pref) {
result.min_pref = left.min_pref;
result.min_idx = left.min_idx;
} else {
result.min_pref = right_pref;
result.min_idx = right.min_idx;
}
return result;
}
void build(int node, int l, int r, const vector<long long>& values) {
if (l == r) {
tree[node] = {values[l], values[l], l};
return;
}
const int mid = (l + r) / 2;
build(node * 2, l, mid, values);
build(node * 2 + 1, mid + 1, r, values);
tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}
void point_update(int node, int l, int r, int index, long long value) {
if (l == r) {
tree[node] = {value, value, l};
return;
}
const int mid = (l + r) / 2;
if (index <= mid) {
point_update(node * 2, l, mid, index, value);
} else {
point_update(node * 2 + 1, mid + 1, r, index, value);
}
tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> b(n + 1);
vector<long long> values(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> b[i];
values[i] = b[i] - 1;
}
SegTree seg(values);
auto emit_answer = [&]() {
const Node root = seg.query_all();
if (root.sum != -1) {
cout << "0 0\n";
return;
}
cout << "1 " << (root.min_idx % n) << '\n';
};
emit_answer();
for (int i = 0; i < q; ++i) {
int x, y;
cin >> x >> y;
++x;
++y;
swap(b[x], b[y]);
seg.point_update(x, b[x] - 1);
seg.point_update(y, b[y] - 1);
emit_answer();
}
return 0;
}
