C. Monoblock

Stanley has decided to buy a new desktop PC made by the company "Monoblock", and to solve captcha on their website, he needs to solve the following task.

The awesomeness of an array is the minimum number of blocks of consecutive identical numbers in which the array could be split. For example, the awesomeness of an array

• [1,1,1][1,1,1] is 11;
• [5,7][5,7] is 22, as it could be split into blocks [5][5] and [7][7];
• [1,7,7,7,7,7,7,7,9,9,9,9,9,9,9,9,9][1,7,7,7,7,7,7,7,9,9,9,9,9,9,9,9,9] is 3, as it could be split into blocks [1][1], [7,7,7,7,7,7,7][7,7,7,7,7,7,7], and [9,9,9,9,9,9,9,9,9][9,9,9,9,9,9,9,9,9].

You are given an array aa of length nn. There are mm queries of two integers ii, xx. A query ii, xx means that from now on the ii-th element of the array aa is equal to xx.

After each query print the sum of awesomeness values among all subsegments of array aa. In other words, after each query you need to calculate

∑l=1n∑r=lng(l,r),∑l=1n∑r=lng(l,r),

where g(l,r)g(l,r) is the awesomeness of the array b=[al,al+1,…,ar]b=[al,al+1,…,ar].

Input

In the first line you are given with two integers nn and mm (1≤n,m≤1051≤n,m≤105).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the array aa.

In the next mm lines you are given the descriptions of queries. Each line contains two integers ii and xx (1≤i≤n1≤i≤n, 1≤x≤1091≤x≤109).

Output

Print the answer to each query on a new line.

题意：

一个子段的awesomeness值是该子段连续相同的数的个数

给一个个数为n的数组a，m次修改

每次修改a[i]为x

求每次修改之后所有子段的awesomeness和

我们设置如果a[i]!=a[i+1]的话那么a[i]就是一个断点

对于一个子段来说，awesomeness值是断点的数量+1

那么对于所有的子段的awesomeness值就是所有断点的贡献加上子段个数个1

对于一个断点来说，他的贡献是所有包含a[i]和a[i+1]的区间的个数：i*(n-i) 

（左边有i个数当开头，后面有n-i个数当结尾，所以区间个数是i*(n-1)  ）

那么答案就是先算出断点的贡献，然后加上子段个数即可

先算出原始数组的断点的贡献

每次修改i的话对i-1和i+1有影响

那么我们就先减去原来的i对i-1和i+1的影响

再加上修改之后的i对i-1和i+1的影响

最后再加上子段的个数即可

/*
 .----------------.  .----------------.  .----------------.  .----------------.
| .--------------. || .--------------. || .--------------. || .--------------. |
| |  ________    | || |  _________   | || | ____    ____ | || |     ____     | |
| | |_   ___ `.  | || | |_   ___  |  | || ||_   \  /   _|| || |   .'    `.   | |
| |   | |   `. \ | || |   | |_  \_|  | || |  |   \/   |  | || |  /  .--.  \  | |
| |   | |    | | | || |   |  _|  _   | || |  | |\  /| |  | || |  | |    | |  | |
| |  _| |___.' / | || |  _| |___/ |  | || | _| |_\/_| |_ | || |  \  `--'  /  | |
| | |________.'  | || | |_________|  | || ||_____||_____|| || |   `.____.'   | |
| |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
#define lowbit(x) x&(-x)
#define PI 3.1415926535
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int b) {
	return b>0 ? gcd(b,a%b):a;
}
/*
int dx[8]={-2,-2,-1,1,2,2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int dx[8]={-1,1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
*/
const int N=1e5+10;
int n,m;
int a[N];
void sove() {
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	a[n+1]=0;
	int ans=0;//存断点贡献
	for(int i=1;i
		ans+=(a[i]!=a[i+1])*i*(n-i);
	}
	while(m--){
		int i,x;
		cin>>i>>x;
		ans-=(a[i]!=a[i+1])*i*(n-i);
		ans-=(a[i-1]!=a[i])*(i-1)*(n-i+1);
		a[i]=x;
		ans+=(a[i]!=a[i+1])*i*(n-i);
		ans+=(a[i-1]!=a[i])*(i-1)*(n-i+1);
		cout<1)/2<
	}
}
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(),cout.tie() ;
	int t=1;
//	cin>>t;
	while(t--) {
		sove();
	}
	return 0;
}