Mohit(Ex GenSec ) is the most active member of the roasting club who loves giving tasks to other members. One day he observed that none of the members were paying attention to the online classes, so he decided to have some fun and overcome the boring lectures. He wrote N numbers on the virtual board (where the first number is 1, the last one is N and the ith number being i).
Then he asked M questions to every other member of the club. In each question, a number K was given by Mohit and the members had to give a single integer as an answer which will be the sum of all numbers present on the whiteboard.
There are some conditions that every member has to follow while answering.
- If K is already present on the whiteboard then swap the first and last number.
- Otherwise, replace the last number with K.

-----Input:-----
- First-line will consist of space-separated integers N and M. The board will contain the list of numbers from 1 to N and M is the number of questions that Mohit will ask.
- Next M lines contain the number Ki, which will be provided by Mohit and (1<=i<=M).

-----Output:-----
For each question, report the sum of all integers present

-----Constraints-----
- $1 \leq N,M \leq 1000000$
- $2 \leq K \leq 10^9$

-----Sample Input:-----
5 4
7
12 
10 
1  

-----Sample Output:-----
17
22  
20
20

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(n, m) = map(int, input().split())
l = n
f = 1
s = n * (n + 1) // 2 - l - f
for _ in range(m):
	k = int(input())
	if 2 <= k <= n - 1 or k in [f, l]:
		(l, f) = (f, l)
	else:
		l = k
	print(s + l + f)


(n, m) = tuple(map(int, input().split()))
if n > 2:
	arr = [1, n]
elif n == 1:
	arr = [1]
elif n == 2:
	arr = [1, 2]
for i in range(m):
	k = int(input())
	if n == 1:
		if k != arr[0]:
			arr[0] = k
		print(arr[0])
	elif n == 2:
		if k == arr[0] or k == arr[1]:
			temp = arr[0]
			arr[0] = arr[1]
			arr[1] = temp
		else:
			arr[1] = k
		print(arr[0] + arr[1])
	else:
		ans = int(n * (n + 1) / 2) - 1 - n
		if k == arr[0] or k == arr[1]:
			temp = arr[0]
			arr[0] = arr[1]
			arr[1] = temp
		elif k > 1 and k < n:
			temp = arr[0]
			arr[0] = arr[1]
			arr[1] = temp
		else:
			arr[1] = k
		ans += arr[0] + arr[1]
		print(ans)


(x, y) = input().split()
x = int(x)
y = int(y)
A = []
n = int()
n = x * (x + 1) / 2
A = [1, x]
ans = []
for i in range(y):
	a = int(input())
	if a not in A and a >= x:
		n = n + a - A[-1]
		A[-1] = a
		ans.append(n)
	else:
		ans.append(n)
		temp = A[0]
		A[0] = A[-1]
		A[-1] = temp
for t in ans:
	print(int(t))


try:

	def performOperations(N, op):
		a = [i for i in range(1, N + 1)]
		m = set(a)
		s = sum(a)
		ans = []
		for i in op:
			if i in m:
				(a[0], a[N - 1]) = (a[N - 1], a[0])
			else:
				s -= a[N - 1]
				s += i
				m.remove(a[N - 1])
				m.add(i)
				a[N - 1] = i
			ans.append(s)
		return ans
	op = []
	(N, m) = map(int, input().split())
	for _ in range(m):
		op.append(int(input()))
	answ = performOperations(N, op)
	for i in answ:
		print(i)
except EOFError as error:
	pass


from collections import defaultdict

def logic(temp, last, n, m):
	if m < 1:
		return
	hash = defaultdict(bool)
	for i in range(1, n + 1):
		hash[i] = True
	temp -= last
	first = 1
	for i in range(m):
		mohit_question = int(input())
		if hash[mohit_question]:
			temp += last
			temp -= first
			(first, last) = (last, first)
			print(temp + last)
		else:
			hash[last] = False
			last = mohit_question
			hash[last] = True
			print(temp + last)

def main():
	(n, m) = list(map(int, input().split()))
	temp = n * (n + 1) // 2
	last = n
	logic(temp, last, n, m)

def __starting_point():
	main()
__starting_point()


from collections import Counter
(n, m) = list(map(int, input().split()))
c = Counter(list(range(1, n + 1)))
s = n * (n + 1) // 2
last = n
first = 1
d = set(list(range(1, n + 1)))
for i in range(m):
	k = int(input())
	if k in d:
		(last, first) = (first, last)
		print(s)
	else:
		s -= last
		d.remove(last)
		d.add(k)
		s += k
		last = k
		print(s)


dic = {}
(n, m) = list(map(int, input().split()))
arr = list(range(1, n + 1))
sm = 0
for i in range(1, n + 1):
	sm += i
	dic[i] = 1
for i in range(m):
	el = int(input())
	if el in dic:
		(arr[0], arr[-1]) = (arr[-1], arr[0])
		print(sm)
	else:
		prev = arr[-1]
		arr[-1] = el
		sm = sm - prev + el
		dic[el] = 1
		del dic[prev]
		print(sm)


try:
	(n, m) = map(int, input().split())
	sum1 = n * (n + 1) / 2
	prev_last = n
	prev_first = 1
	sum_mid = sum1 - (prev_first + prev_last)
	while m:
		k = int(input())
		if k >= 2 and k <= n - 1 or k == prev_first or k == prev_last:
			(prev_last, prev_first) = (prev_first, prev_last)
		else:
			prev_last = k
		print(int(sum_mid + prev_last + prev_first))
		m -= 1
except:
	pass