RPG

Time limit: 1 s.
Memory limit: 256 MB

You are playing a game with \(N\) monsters arranged in a line. The strength of the \(i\)-th monster is \(A_i\).

Initially, your power is \(0\).

You fight the monsters from left to right. If you encounter a monster with strength strictly greater than your current power, you defeat it, your power becomes equal to its strength, and you immediately restart from the first monster.

You continue this process until you can pass through the entire line without increasing your power.

The number of times you restart is called the answer.

You are also given \(Q\) updates. Each update is of the form \((i, k)\), meaning that the strength of monster \(i\) increases by \(k\).

Note: Updates persist between queries, but your power resets back to \(0\) before each query.

After each update, print the answer.

Input

The first line contains two integers \(N\) and \(Q\). \((1 \le N, Q \le 2 \cdot 10^5)\)

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\). \((1 \le A_i \le 10^9)\)

Each of the next \(Q\) lines contains two integers \(i\) and \(k\). \((1 \le i \le N,\; 1 \le k \le 10^9)\)

For each update, increase \(A_i\) by \(k\).

Output

For each query, print a single integer — the number of restarts required after applying the update.

Scoring

Group Constraints Points
\(1\) \(N, Q \le 200\) \(13\)
\(2\) \(Q = 1\) \(17\)
\(3\) \(i = 1\) \(23\)
\(4\) \(i = N\) \(11\)
\(5\) \(i\) is constant over all queries \(7\)
\(6\) — \(29\)

Example

Input

3 3
3 4 5
3 1
2 3
1 10

Output

3
2
1

Note

Note

  • After the first update \((3,1)\), the array becomes \([3,4,6]\).

    • First run: power changes from \(0\) to \(3\).
    • Second run: power changes from \(3\) to \(4\).
    • Third run: power changes from \(4\) to \(6\).
    • Fourth run: no change happens, so the process stops.

    The power increased \(3\) times, so the answer is \(3\).

  • After the second update \((2,3)\), the array becomes \([3,7,6]\).

    • First run: power changes from \(0\) to \(3\).
    • Second run: power changes from \(3\) to \(7\).
    • Third run: no change happens, so the process stops.

    The power increased \(2\) times, so the answer is \(2\).

  • After the third update \((1,10)\), the array becomes \([13,7,6]\).

    • First run: power changes from \(0\) to \(13\).
    • Second run: no change happens, so the process stops.

    The power increased \(1\) time, so the answer is \(1\).

Solution

Every restart raises the power to the next strict prefix maximum of the array. Therefore, the answer is exactly the number of strict prefix maxima.

Keep their indices in an ordered set. After increasing \(A_i\):

  • if \(i\) is already a prefix maximum, it remains one;
  • otherwise, it becomes one exactly when it exceeds the previous prefix maximum;
  • if \(i\) is a prefix maximum, remove every following prefix maximum whose value is no larger than \(A_i\).

An index can be inserted or erased only after an update, so the total complexity is \(O((N+Q)\log N)\) and the memory usage is \(O(N)\).

#include <iostream>
#include <set>
#include <vector>
using namespace std;

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

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    set<int> records;
    long long maximum = -1;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > maximum) {
            maximum = a[i];
            records.insert(i);
        }
    }

    while (q--) {
        int index;
        long long increase;
        cin >> index >> increase;
        index--;
        a[index] += increase;

        auto it = records.lower_bound(index);

        if (it == records.end() || *it != index) {
            int previous = *prev(it);
            if (a[index] > a[previous]) {
                it = records.insert(index).first;
            } else {
                cout << records.size() << '\n';
                continue;
            }
        }

        auto next = std::next(it);
        while (next != records.end() && a[*next] <= a[index]) {
            next = records.erase(next);
        }

        cout << records.size() << '\n';
    }
}