Problem Description

In Cesenatico there is a tall building with $N$ floors, and one resident lives on each floor. The floors are numbered from bottom to top as $0$ to $N - 1$, and resident $r$ lives on floor $r$.

Each floor has a balcony where residents can enjoy the sun and grow some flowers. They can also enjoy the flowers on the balconies below. Since all flowers must be watered every day, everyone decides to help each other. Each resident can water the flowers for the resident living one floor below.

Every morning, all residents leave the building at time 0. Initially, resident $r$ comes back home at time $t_r$. If resident $r$ comes back strictly earlier than the one living below, that is, $t_r < t_{r - 1}$, then resident $r$ will water the flowers for resident $r - 1$. (Otherwise, resident $r - 1$ must water their own flowers.) At the end of each day, one of the following two events happens:

• Type !: Some resident $r$ updates their return time, effective starting from the next day.
• Type ?: Some resident $r$ asks how many times they have watered the flowers for resident $r - 1$.

Note that resident $0$ will not water for anyone, and the flowers of resident $N - 1$ will never be watered by anyone else.

Your task is to help the residents answer all queries of type ?.

Input Format

The first line contains two integers $N$ and $D$, representing the number of residents and the number of days to track.

The next line contains $N$ integers $t_0, t_1, \cdots, t_{N-1}$, the initial return times of the residents.

Then there are $D$ lines. The $i$-th line describes the event that happens at the end of day $i$.

Each event has one of the following formats:

• ! r x. Resident $r$ ($0 \leq r \leq N-1$) will return home at time $x$ starting from the next day, i.e. the value of $t_r$ becomes $x$. Note that $x$ may be the same as the current $t_r$.
• ? r. Ask, for resident $r$ ($1 \leq r \leq N-1$), how many times in total they have watered the flowers for resident $r - 1$ since day $0$.

It is guaranteed that there is at least one ? event.

Output Format

For each ? event, output one line with one integer: the number of times resident $r$ has watered the flowers for resident $r - 1$ since day $0$.

Note: In this problem, do not count the times a resident waters their own flowers.

3 4
7 7 5
? 2
? 1
? 2
? 2

1
0
3
4

2 5
5 7
! 1 4
? 1
! 0 4
! 1 6
? 1

1
2

4 6
13 9 15 2
! 1 18
? 3
! 0 12
! 2 1
? 1
? 2

2
1
5

3 6
5 2 4
? 1
! 1 8
! 0 10
! 1 3
? 1
? 2

1
4
2

Hint

Sample Explanation

:::align{center}

Sample 1. A watering-can icon means that this resident will water the flowers for the neighbor below. :::

The first sample applies to subtasks 2, 4, 5, and 6. Since the schedule is never updated, resident $2$ comes home earlier than resident $1$ every day and waters their flowers. After day $0$, resident $2$ has watered the neighbor once. Since residents $0$ and $1$ return home at the same time, resident $1$ will not water for resident $0$. After day $1$, resident $1$ still has never watered the neighbor. After day $2$, resident $2$ has watered the neighbor three times. After day $3$, resident $2$ has watered the neighbor four times.

:::align{center}

Sample 2. :::

The second sample applies to subtasks 3, 4, and 6. On day $0$, resident $1$ does not water the neighbor. After day $0$, resident $1$'s schedule is updated. Since on day $1$ they return home earlier than the neighbor, they water the flowers. After day $1$, resident $1$ has watered the neighbor once. On day $2$, resident $1$ waters the neighbor again. After day $4$, resident $1$ has watered the neighbor a total of two times.

The third sample applies to subtasks 4, 5, and 6. Note that this sample has no illustration.

:::align{center}

Sample 4. :::

The fourth sample applies to subtasks 4 and 6. After day $0$, resident $1$ watered the neighbor once. After day $4$, resident $1$ watered the neighbor four times (on days $0$, $1$, $3$, and $4$). Resident $2$ watered the neighbor a total of two times (on days $2$ and $3$).

Constraints

• $2 \leq N \leq 200\ 000$.
• $1 \leq D \leq 200\ 000$.
• $1 \leq t_r \leq 10^9$ (initially and after each change).

Scoring

Your program will be tested on testdata split into several subtasks. To get the score for a subtask, you must solve all testdata in that subtask correctly.

• Subtask $0$ [$0$ points]: Samples.
• Subtask $1$ [$9$ points]: $D = 1$, i.e. there is only one ? event.
• Subtask $2$ [$12$ points]: All events are of type ?.
• Subtask $3$ [$13$ points]: $N = 2$.
• Subtask $4$ [$18$ points]: $N \le 2000$ and $D \le 2000$.
• Subtask $5$ [$21$ points]: Each resident changes their return time at most once.
• Subtask $6$ [$27$ points]: No additional constraints.

Translated by ChatGPT 5