Screen Saver

Sang-geun installed a new screen saver. When the computer is left idle for $5$ minutes, the screen saver starts and shows an aquarium with fish swimming inside it. On the settings screen you can change the shape of the aquarium floor and the height of the water surface.

The aquarium is drawn as a 2D plane of width $N-1$. The leftmost $x$-coordinate is $0$ and the rightmost is $N-1$, and every integer $x$-coordinate $i$ has a floor height $H_i$. The floor consists of, for each pair of adjacent coordinates $i$ and $i+1$, the line segment joining the points $(i, H_i)$ and $(i+1, H_{i+1})$.

If the water surface is at height $h$, all of the space between the floor and the line $y = h$ is filled with water. Any part of the floor that rises above $h$ becomes an island that is not submerged.

Every time Sang-geun changes a floor height or the water surface height, he wants to know the area of the region currently filled with water.

The first line contains two positive integers $N$ and $M$, where $M$ is the number of changes Sang-geun makes. ($3 \le N \le 100{,}000$, $1 \le M \le 100{,}000$)

The second line contains the initial floor heights $H_0, H_1, \dots, H_{N-1}$, separated by spaces. ($0 \le H_i \le 1000$)

Each of the next $M$ lines describes one change, in one of the following two forms.

• Q h : set the water surface height to $h$. ($0 \le h \le 1000$)
• U i h : set the floor height at $x$-coordinate $i$ to $h$, i.e. $H_i = h$. ($0 \le i \le N-1$, $0 \le h \le 1000$)

For every change that begins with Q, print the area of the region filled with water at that moment, to three decimal places.