B'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 You are given an array a of length n . There are m queries of two integers i , x . A query i , x means that from now on the i -th element of the array a is equal to x . After each query print the sum of awesomeness values among all subsegments of array a . In other words, after each query you need to calculate sum limits_{l = 1}^n sum limits_{r = l}^n g(l, r), where g(l, r) is the awesomeness of the array b = [a_l, a_{l + 1}, ldots, a_r] . In the first line you are given with two integers n and m ( 1 <= q n, m <= q 10^5 ). The second line contains n integers a_1, a_2, ldots, a_n ( 1 <= a_i <= 10^9 ) -- the array a . In the next m lines you are given the descriptions of queries. Each line contains two integers i and x ( 1 <= q i <= q n , 1 <= q x <= q 10^9 ). Print the answer to each query on a new line. After the first query a is equal to [1, 2, 2, 4, 5] , and the answer is 29 because we can split each of the subsegments the following way: '...