Historical Graze Queries

You are given a sequence of n positive integers \(a_1, a_2, \dots, a_n\). The graze value between two positions \(x\) and \(y\) is defined as

\(\text{graze}(x,y)=|x-y|+|a_x - a_y|\)

You have to support the following two types of operations (\(k\) is always a positive integer):

• Modify x k: change the value at position \(x\) to \(k\).
• Query x k: count the number of pairs \((x,i)\) satisfying \(\text{graze}(x,i) \leq k\).

Note that when processing a query, you must consider all historical versions of the sequence. In other words, every time a value (even if repeated) appears at any position (including the initial sequence and every subsequent modification), it is counted. For a query, let \(a_x\) denote the current value at position \(x\); then for every occurrence of a value \(v\) at position \(i\) that has ever appeared, if

\(|x-i| + |a_x - v| \leq k\),

it contributes to the answer.

inputFormat

The first line contains two space-separated integers \(n\) and \(q\): the length of the sequence and the number of operations.

The second line contains \(n\) space-separated positive integers \(a_1, a_2, \dots, a_n\) representing the initial sequence.

Each of the next \(q\) lines contains an operation in one of the following formats:

• Modify x k: Change the value at position \(x\) to \(k\).
• Query x k: Count the number of historical occurrences (across any position and any time) such that if \(a_x\) is the current value at position \(x\), then for an occurrence of a value \(v\) at position \(i\), \(|x-i| + |a_x - v| \leq k\).

outputFormat

For each Query operation, output a single integer on a new line representing the answer to that query.

sample

3 3
1 2 3
Query 2 2
Modify 3 1
Query 2 2

3
4