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

Difficulty: interview

Starter code:

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)

# cook your dish here

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))
 



# cook your dish here
try:
 def performOperations(N, op):
 # Write your code here
 # print(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 #swap 
     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 #total sum 
  
  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:
  ## swap
  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)



# cook your dish here
# cook your dish here
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