CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

sub = []
for i in range(n):
    sub.append(a[i] - i - 1)
sub.sort()

def geta(b):
    un=0
    for i in range(n):
        un+=abs(sub[i]-b)
    return un

med = sub[n//2]
ans=geta(med)
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

sub = []
for i in range(n):
    sub.append(a[i] - i - 1)
sub.sort()

def geta(b):
    un=0
    for i in range(n):
        un+=abs(sub[i]-b)
    return un

med = sub[n//2]
ans=10**20
for i in range(med-1,med+1):
    num = geta(i)
    if ans > num:
        ans=num
print(ans)
# Original solution
n = int(eval(input()))
l = list(map(int,input().split()))

m = []
for i in range(n):
    m.append(l[i]-i)

b = set(m)
max = 0
index = 0
for i in b:
    if max < m.count(i):
        max = m.count(i)
        index = i

ans = 0
for i in range(n):
    ans += abs(l[i]-index-i)

print(ans)


# Optimized solution
n = int(eval(input()))
l = list(map(int,input().split()))

m = []
for i in range(n):
    m.append(l[i]-i-1)

m.sort()
index = n//2

b = m[index]

ans = 0
for i in range(n):
    ans += abs(l[i]-b-i-1)

print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i - (i))
A_dash.sort()

tmp_ans = sum(A_dash)
ans = 0
left, right = min(A_dash), max(A_dash)
mid = (left+right)//2
ans_left, ans_mid, ans_right = 0, 0, 0
for A_dash_i in A_dash:
    ans_left += abs(A_dash_i - (mid-1))
    ans_mid += abs(A_dash_i - (mid))
    ans_right += abs(A_dash_i - (mid+1))

while not (ans_left >= ans_mid and ans_mid <= ans_right):
    mid = (left+right)//2
    ans_left, ans_mid, ans_right = 0, 0, 0
    for A_dash_i in A_dash:
        ans_left += abs(A_dash_i - (mid-1))
        ans_mid += abs(A_dash_i - (mid))
        ans_right += abs(A_dash_i - (mid+1))
    if ans_left < ans_mid:
        right = (left+right)//2
    else:
        left = (left+right)//2

print(ans_mid)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i-(i+1))
A_dash.sort()

med = A_dash[N//2]

ans = 0
for i, A_i in enumerate(A_dash):
    ans += abs(A_i - (med))

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))


def sadness(b):
  sad = 0
  for i, e in enumerate(a):
    i += 1
    sad += abs(e - (b + i))
  return sad


left, right = -10**9, 10**9 + 1
while right - left > 1:
  mid = (left + right) // 2

  if sadness(mid) > sadness(mid + 1):
    left = mid
  else:
    right = mid

# for b in range(-20, 20):
#   print(b,sadness(b))

print((min(sadness(left), sadness(right))))


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))


def sadness(b):
  sad = 0
  for i, e in enumerate(a):
    i += 1
    sad += abs(e - (b + i))
  return sad


d = []
for i, e in enumerate(a):
  i += 1
  d.append(e - i)

d.sort()

if len(d) % 2 == 1:
  print((sadness(d[len(d) // 2])))
else:
  print((min(sadness(d[len(d) // 2]), sadness(d[len(d) // 2 + 1]))))
# Original solution
def main():
    from decimal import Decimal

    N = int(eval(input()))
    *A, = list(map(Decimal, input().split()))
    A = [x - i for i, x in enumerate(A, start=1)]
    A.sort()

    median = -1
    if N % 2 == 1:
        median = A[N // 2]
    else:
        median = (A[N // 2 - 1] + A[N // 2]) / 2  # ->ここで0.5が生じても偶数個足し合わせてintに戻る

    ans = sum([abs(x - median) for x in A])
    print((int(ans)))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N = int(eval(input()))
    A = [x - i for i, x in enumerate(map(int, input().split()), start=1)]
    A.sort()

    m = A[N // 2]  # 個数の偶奇によらず、この点は絶対値の総和を最小にする

    ans = sum(abs(x - m) for x in A)

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    a = LI()
    for i in range(n):
        a[i] -= i+1
    a.sort()
    ans = float("inf")
    for b in a:
        m = 0
        for i in range(n):
            m += abs(a[i]-b)
        ans = min(ans,m)
    print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    a = LI()
    for i in range(n):
        a[i] -= i+1
    a.sort()
    b = sum(a)//n
    ans = 0
    for i in range(n):
        ans += abs(a[i]-b)
    ans2 = 0
    b += 1
    for i in range(n):
        ans2 += abs(a[i]-b)
    ans3 = 0
    b = a[n//2]
    for i in range(n):
        ans3 += abs(a[i]-b)
    print((min(ans,ans2,ans3)))

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()
# Original solution
import sys
import math

N = int(eval(input()))
A = [int(x) for x in input().split()]

A2 = [a - i - 1 for i, a in enumerate(A)]

B = sorted(A2)

i1 = int(N/2) - 1
i2 = int(N/2)


b1 = B[i1]
b2 = B[i2]


def calcSad(A2, b):
    sum = 0
    for i in A2:
        sum += abs(i - b)
    return sum


sum = 99999999999999999999999
for b in range(b1, b2+1):
    s = calcSad(B, b)
    sum = min(sum, s)

print(sum)


sys.exit(0)


# Optimized solution
import sys
import math

N = int(eval(input()))
A = [int(x) for x in input().split()]
A2 = [a - i - 1 for i, a in enumerate(A)]

B = sorted(A2)

b = B[int(N/2)]


A3 = [abs(a - b) for a in A2]

print((sum(A3)))


sys.exit(0)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
minb=min(min(A),max(A)-N)
maxb=max(max(A),min(A)+N)
ans=float('inf')
for b in range(minb,maxb+1):
  d=0
  for i in range(N):
    d+=abs(A[i]-(b+i))
  ans=min(ans,d)
print(ans)

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i]-(i+1))
B.sort()
b=B[N//2]
ans=0
for i in range(N):
  ans+=abs(B[i]-b)
print(ans)
# Original solution
# coding: utf-8
import math
n = int(eval(input()))
#x, y = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
B=  []
for i in range(n):
    B.append(A[i]-(i+1))
B.sort()
if n==1:
    m=B[0]
    m2=B[0]
else:
    m = B[n//2]
    m2=B[n//2+1]
tmp1=0
tmp2=0
#print(m,m2)
for i in range(n):
    tmp1 += abs(A[i]-(i+1)-m)
    tmp2 += abs(A[i]-(i+1)-m2)
print((min(tmp1, tmp2)))

# Optimized solution
# coding: utf-8
n = int(eval(input()))
A = list(map(int,input().split()))
L=[]
for i in range(n):
    L.append(A[i]-(i+1))
L.sort()
#print(L)
if n==1:
    b1=L[0]
    b2=L[0]
elif n==2:
    b1=L[0]
    b2=L[1]
else:
    b1=L[n//2]
    b2=L[n//2-1]
ans=0
cnt1=0
cnt2=0
for i in range(n):
    cnt1+=abs(L[i]-b1)
    cnt2+=abs(L[i]-b2)
print((min(cnt1,cnt2)))
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
a = sorted(x - i for i, x in enumerate(a))
low = (len(a) + 1) // 2 - 1
high = len(a) // 2
print((sum(a[high:]) - sum(a[:low + 1])))


# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = list(map(int, read().split()))
a = sorted(aa - i for i, aa in enumerate(a))
print((sum(a[n // 2:]) - sum(a[:(n + 1) // 2])))
# Original solution
def main(n,a):
  a=sorted([a[i]-i for i in range(n)])
  m0=a[n//2]
  m1=a[n//2-1]
  ans0,ans1=0,0
  for i in range(n):
    ans0+=abs(a[i]-m0)
    ans1+=abs(a[i]-m1)
  print((min(ans0,ans1)))
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(eval(input()))
  a=list(map(int,input().split()))
  main(n,a)


# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
a=[x-i-1 for i,x in enumerate(a)]
a.sort()
b=a[n//2]
print((sum([abs(x-b) for x in a])))
# Original solution
n=int(eval(input()))
l=list(map(int,input().split()))
l=[x-i-1 for i,x in enumerate(l)]
ans=10**9
for i in l:
    cal=[abs(x-i) for x in l]
    ans=min(ans,sum(cal))
print(ans)

# Optimized solution
n=int(eval(input()))
l=list(map(int,input().split()))
l=sorted([x-i-1 for i,x in enumerate(l)])
x=l[n//2]
print((sum([abs(i-x) for i in l])))
# Original solution
#coding:utf-8
n = int(eval(input()))
nums = sorted([num - i for i, num in enumerate(list(map(int,input().split())), 1)])


sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)

minv = nums[0] * (2 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    for b in range(nums[i], nums[i+1]+1):
        p = b * (2*(i+1) - n) -2 * sums[i] + allv
        minv = min(minv,p)

print(minv)

# Optimized solution
#coding:utf-8
n = int(eval(input()))
nums = sorted([num - i for i, num in enumerate(list(map(int,input().split())), 1)])


sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)

minv = nums[0] * (2 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    p = nums[i] * (2*(i+1) - n) -2 * sums[i] + allv
    minv = min(minv,p)

print(minv)
# Original solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t = a[n // 2]
    mt = 0
    for v in a:
        mt += abs(t - v)
    print(mt)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t = 0
    for v in a:
        t += abs(a[n // 2] - v)
    print(t)


if __name__ == '__main__':
    solve()
# Original solution
N = int(eval(input()))
src = list(map(int,input().split()))

mem = [a-i-1 for i,a in enumerate(src)]
center = sorted(mem)[N//2]

ans = 0
for a in mem:
    ans += abs(a - center)
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = [a-i for i,a in enumerate(A)]
B.sort()
m = B[N//2]
ans = 0
for b in B:
    ans += abs(m-b)
print(ans)
# Original solution
a = int(eval(input()))
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
s = 0
co = 0
ss = 0
coco = 0
cococo = 0
summ = 0
su = 0
bb = 0
for i in range(a):
	if b[i] < 0:
		co += 1
	elif b[i] > 0:
		coco += 1
	else:
		cococo += 1
	su += abs(b[i])

if co > coco:	
	while su != 0:
		bb = 0
		for i in range(a):
			b[i] += 1
			bb += abs(b[i])
		if bb > su:
			print(su)
			break
		su = bb
		bb = 0


elif coco >= co:
	while su != 0:
		for i in range(a):
			b[i] -= 1
			bb += abs(b[i])
		if bb > su:
			print(su)
			break
		su = bb
		bb = 0

if su == 0:
	print((0)) 

# Optimized solution
a = int(eval(input()))
b = list(map(int,input().split()))
 
for i in range(a):
	b[i] -= i + 1
 
b.sort()
su = 0
c = b[(a - 1) // 2]

for i in range(a):
	su += abs(b[i] - c)

print(su)
# Original solution
import math
N=int(eval(input()))
A=list(map(int,input().split()))

B=[A[i]-i for i in range(N)]
B.sort()
temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)



# Optimized solution
import math
N=int(eval(input()))
A=list(map(int,input().split()))

B=[A[i]-(i+1) for i in range(N)]
B.sort()
temp=0

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)
# Original solution
def func(A,b):
  s=0
  for i in range(len(A)):
    s+=abs(A[i]-(b+i))
  return s

N=int(eval(input()))
A=[int(i) for i in input().split(' ')]
MIN=None
for b in range(min(A[0],A[-1]-len(A)),max(A[-1],A[0]+len(A))):
  if MIN==None:
    MIN=func(A,b)
  elif MIN>func(A,b):
    MIN=func(A,b)
print(MIN)

# Optimized solution
N=int(eval(input()))
A=[int(i) for i in input().split(' ')]
for i in range(len(A)):
  A[i]-=i+1
A.sort()
if len(A)%2==1:
  b=A[(len(A)-1)//2]
else:
  b=A[(len(A))//2-1]
s=0
for i in range(len(A)):
  s+=abs(A[i]-b)
print(s)
# Original solution
from statistics import median
n=int(eval(input()))
a=list(map(int,input().split()))
mid=0
l=[]
for i in range(n):
    l+=[a[i]-i-1]

mid=median(l)
ans=0
for i in range(n):
    ans+=abs(a[i]-(mid+i+1))

print((int(ans)))

# Optimized solution
from statistics import median
n=int(eval(input()))
a=list(map(int,input().split()))
mid=0
l=[]
for i in range(n):
    l+=[a[i]-i-1]

mid=median(l) if n%2!=0 else sorted(l)[n//2]
ans=0
for i in range(n):
    ans+=abs(a[i]-(mid+i+1))

print((int(ans)))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
answer = 0
r = 0
flag = 0
gear = 0
for i in range(N) :
    A[i] = A[i]-(i+1)
    if A[i] <= 0 :
        r += 1
    answer += abs(A[i])
if r == N :
    gear += 1
while flag == 0 :
    p = 0
    q = 0
    if gear == 0 :
        for j in range(N) :
            A[j] = A[j]-1
            if A[j] <= 0 :
                q += 1
            p += abs(A[j])
    else :
        for j in range(N) :
            A[j] = A[j]+1
            if A[j] >= 0 :
                q += 1
            p += abs(A[j])
    if p < answer :
        answer = p
    if q == N :
        flag += 1
print(answer)


# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
answer = 0
for i in range(N) :
    A[i]-= i+1
A = sorted(A)
if N % 2 != 0 :
    a = A[N//2]
else :
    a = (A[N//2]+A[N//2-1])//2
for j in range(N) :
    A[j] -= a
    answer += abs(A[j])
print(answer)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = []
for i in range(N):
    B.append(A[i]-i-1)
B.sort()
med = N // 2
grief = 0
for i in range(N):
    grief += abs(B[i]-B[med])
print((str(grief)))

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = []
for i in range(N):
    A[i] -= i+1
A.sort()
#for i in range(N):
#    B.append(A[i]-i-1)
#B.sort()
med = N // 2
grief = 0
for i in range(N):
    grief += abs(A[i]-A[med])
#for i in range(N):
#    grief += abs(B[i]-B[med])
print((str(grief)))
# Original solution
import statistics

N = int(eval(input()))
A = list(map(int, input().split()))
A = [a - i for i, a in enumerate(A, 1)]

b = statistics.median(A)
ans = int(sum([abs(a-b) for a in A]))
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A = sorted([a - i for i, a in enumerate(A, 1)])

b = A[(N - 1)//2]
ans = sum([abs(a-b) for a in A])
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
L = []
for i in range(N):
  L.append(A[i]-i-1)
L.sort()
k = 0
if (N%2 == 0):
  k = (L[(N//2)-1]+L[N//2])/2
else:
  k = L[N//2]
ans = 0
for i in range(N):
  ans += abs(L[i]-k)
print((int(ans)))

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
L = [0]*N
for i in range(N):
  L[i] = A[i]-i-1
L.sort()
S = 0
if len(L)%2 != 0:
  k = L[len(L)//2]
  for i in range(len(L)):
    S += abs(L[i]-k)
else:
  k = (L[len(L)//2-1]+L[len(L)//2])//2
  for i in range(len(L)):
    S += abs(L[i]-k)
print(S)
# Original solution
n,a,b=map(int,input().split())
s=input()
ans=list('No'for _ in range(n))
c=a+b
for i in range(n):
    if ans[:i].count('Yes')<c:
        if s[i]=='a':
            ans[i]='Yes'
        if s[i]=='b' and s[:i].count('b')<b:
            ans[i]='Yes'
            
            

print(*ans,sep='\n')


# Optimized solution
n,a,b=map(int,input().split())
s=input()
ans=list('No'for _ in range(n))
c=a+b
countY=0
countb=0
for i in range(n):
    if countY<c:
        if s[i]=='a':
            ans[i]='Yes'
            countY+=1
        if s[i]=='b' and countb<b:
            ans[i]='Yes'
            countY+=1
            countb+=1
            
print(*ans,sep='\n')
# Original solution
from sys import stdin
from math import ceil, floor
n, a, b = [int(x) for x in stdin.readline().rstrip().split()]
s = list(stdin.readline().rstrip())
d = 0
e = 0
for i in range(n):
    if d < a + b and s[i] == "a":
        print("Yes")
        d += 1
    elif d < a + b and e < b and s[i] == "b":
        print("Yes")
        d += 1
        e += 1
    else:
        print("No")

# Optimized solution
from sys import stdin
from math import ceil, floor
n,a,b = [int(x) for x in stdin.readline().rstrip().split()]
s=list(stdin.readline().rstrip())
c=a+b
d=e=0
for i in range(n):
    if d<c and s[i]=="a":
        print("Yes")
        d+=1
    elif d<c and e<b and s[i]=="b":
        print("Yes")
        d+=1
        e+=1
    else:
        print("No")
# Original solution
n,a,b = map(int,input().split())
s = input()
ans = ["0"]*n
bcnt = 0
for i in range(n):
  if s[i] == "a":
    if ans.count("Yes") < a+b:
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  elif s[i] == "b":
    bcnt += 1
    if ans.count("Yes") < a+b and bcnt <= b:
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  else:
    ans[i] = "No"
print(*ans,sep='\n')


# Optimized solution
n,a,b = map(int,input().split())
s = input()
ans = ["0"]*n
acnt = 0
bcnt = 0
for i in range(n):
  if s[i] == "a":
    if acnt < a+b:
      acnt += 1
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  elif s[i] == "b":
    bcnt += 1
    if acnt < a+b and bcnt <= b:
      acnt += 1
      ans[i] = "Yes"
    else:
      ans[i] = "No"
  else:
    ans[i] = "No"
print(*ans,sep='\n')
# Original solution
class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

N, M = list(map(int, input().split()))
uf = UnionFind(N)

# 最後は全部つながってない
# うしろから順番につなぐ
edges = []
for _ in range(M):
    ai, bi = list(map(int, input().split()))
    ai, bi = ai - 1, bi - 1
    edges.append((ai, bi))
edges.reverse()

ans = [N * (N - 1) // 2]
for (ai, bi) in edges:
    u1 = uf.group_count()
    if not uf.same(ai, bi):
        ans.append(ans[-1] - uf.size(ai) * uf.size(bi))
    else:
        ans.append(ans[-1])
    uf.unite(ai, bi)

for a in ans[::-1][1:]:
    print(a)

# Optimized solution
class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

N, M = list(map(int, input().split()))
uf = UnionFind(N)

# 最後は全部つながってない
# うしろから順番につなぐ
edges = []
for _ in range(M):
    ai, bi = list(map(int, input().split()))
    ai, bi = ai - 1, bi - 1
    edges.append((ai, bi))
edges.reverse()

ans = [N * (N - 1) // 2]
for (ai, bi) in edges:
    if not uf.same(ai, bi):
        ans.append(ans[-1] - uf.size(ai) * uf.size(bi))
    else:
        ans.append(ans[-1])
    uf.unite(ai, bi)

for a in ans[::-1][1:]:
    print(a)