Acingel is a small town. There was only one doctor here — Miss Ada. She was very friendly and nobody has ever said something bad about her, so who could've expected that Ada will be found dead in her house? Mr Gawry, world-famous detective, is appointed to find the criminal. He asked $m$ neighbours of Ada about clients who have visited her in that unlucky day. Let's number the clients from $1$ to $n$. Each neighbour's testimony is a permutation of these numbers, which describes the order in which clients have been seen by the asked neighbour.

However, some facts are very suspicious – how it is that, according to some of given permutations, some client has been seen in the morning, while in others he has been seen in the evening? "In the morning some of neighbours must have been sleeping!" — thinks Gawry — "and in the evening there's been too dark to see somebody's face...". Now he wants to delete some prefix and some suffix (both prefix and suffix can be empty) in each permutation, so that they'll be non-empty and equal to each other after that — some of the potential criminals may disappear, but the testimony won't stand in contradiction to each other.

In how many ways he can do it? Two ways are called different if the remaining common part is different.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $1 \le m \le 10$) — the number of suspects and the number of asked neighbors.

Each of the next $m$ lines contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that these integers form a correct permutation (that is, each number from $1$ to $n$ appears exactly once).


-----Output-----

Output a single integer denoting the number of ways to delete some prefix and some suffix of each permutation (possibly empty), such that the remaining parts will be equal and non-empty.


-----Examples-----
Input
3 2
1 2 3
2 3 1

Output
4

Input
5 6
1 2 3 4 5
2 3 1 4 5
3 4 5 1 2
3 5 4 2 1
2 3 5 4 1
1 2 3 4 5

Output
5

Input
2 2
1 2
2 1

Output
2



-----Note-----

In the first example, all possible common parts are $[1]$, $[2]$, $[3]$ and $[2, 3]$.

In the second and third examples, you can only leave common parts of length $1$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Combinatorics

Amortized analysis

Mathematics

Complete search


Solutions:
def get_sub_array(array):
	d = {}
	st = 0
	en = 0
	while st < len(array) and en < len(array):
		if en < len(array) - 1 and array[en + 1] == array[en] + 1:
			en += 1
		else:
			d[array[st]] = en - st + 1
			st += 1
			en = st if en < st else en
	return d
(n, m) = [int(x) for x in input().split()]
array = []
for i in range(m):
	array.append([int(x) for x in input().split()])
d = dict()
for i in range(1, n + 1):
	d[array[0][i - 1]] = i
for i in range(m):
	for j in range(n):
		array[i][j] = d[array[i][j]]
res = [float('inf') for i in range(n)]
dm = []
for i in range(m):
	dm.append(get_sub_array(array[i]))
for i in range(1, n + 1):
	for j in range(m):
		res[i - 1] = min(res[i - 1], dm[j][i])
print(sum(res))


import sys
input = sys.stdin.readline
(n, m) = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for i in range(m)]
LISTS = [[None for i in range(n + 1)] for i in range(m)]
for i in range(n):
	for j in range(m):
		LISTS[j][A[j][i]] = i
ANS = 0
i = 0
while i < n:
	x = A[0][i]
	check = 1
	for j in range(i + 1, n + 1):
		for k in range(1, m):
			if LISTS[k][x] + (j - i) < n and j < n and (A[k][LISTS[k][x] + (j - i)] == A[0][j]):
				continue
			else:
				check = 0
				break
		if check == 0:
			break
	ANS += (j - i) * (j - i + 1) // 2
	i = j
print(ANS)


(n, m) = map(int, input().split())
initial = []
first = input().split()
for i in range(n):
	initial.append(int(first[i]))
rest = []
for i in range(m - 1):
	current = []
	nfirst = input().split()
	for j in range(n):
		current.append(int(nfirst[j]))
	rest.append(current)
index = 0
compar = 0
ans = 0
indices = []
for i in range(m - 1):
	temp = [0] * n
	x = rest[i]
	for j in range(n):
		temp[x[j] - 1] = j
	indices.append(temp)
while index < n:
	compar = initial[index]
	cur = [0] * (m - 1)
	count = 1
	lol = n - index
	for k in range(m - 1):
		cur[k] = indices[k][compar - 1]
		lol = min(lol, n - cur[k])
	done = False
	while count < lol:
		for k in range(m - 1):
			x = rest[k]
			j = cur[k]
			if x[j + count] != initial[index + count]:
				done = True
				break
		if done:
			break
		count += 1
	ans += count * (count + 1) // 2
	index += count
print(ans)


(n, m) = map(int, input().split())
a = [[*map(lambda x: int(x) - 1, input().split())] for _ in range(m)]
idx = [[0] * n for _ in range(m)]
for i in range(m):
	for j in range(n):
		idx[i][a[i][j]] = j
l = ans = 0
r = 1
while r < n:
	flag = True
	for i in range(1, m):
		if idx[i][a[0][r]] - idx[i][a[0][r - 1]] != 1:
			flag = False
			break
	if not flag:
		ans += (r - l) * (r - l + 1) // 2
		l = r
	r += 1
ans += (r - l) * (r - l + 1) // 2
print(ans)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	(n, m) = map(int, input().split())
	a = [list(map(lambda x: int(x) - 1, input().split())) + [-1] for _ in range(m)]
	(p, v, ans) = ([[0] * n for _ in range(m)], [0] * n, 0)
	for i in range(m):
		for j in range(n):
			p[i][a[i][j]] = j
	for i in range(n):
		if not v[a[0][i]]:
			(l, v[a[0][i]]) = (1, 1)
			for j in range(i + 1, n):
				f = 1
				for k in range(1, m):
					if a[k][p[k][a[0][j - 1]] + 1] != a[0][j]:
						f = 0
						break
				if f:
					v[a[0][j]] = 1
					l += 1
				else:
					break
			ans += l * (l + 1) // 2
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(N, M) = list(map(int, input().split()))
A = []
loc = [{} for _ in range(M)]
for i in range(M):
	a = [int(x) for x in input().split()]
	A.append(a)
	for (iv, v) in enumerate(a):
		loc[i][v] = iv
ans = 0
ls = [0] * M
i = 0
while i < N:
	v = A[0][i]
	ls = [loc[j][v] for j in range(M)]
	segl = 1
	while all([l + segl < N for l in ls]) and all((A[il][l + segl] == A[0][ls[0] + segl] for (il, l) in enumerate(ls))):
		segl += 1
	ans += segl * (segl + 1) // 2
	i += segl
print(ans)


import math
import sys
from decimal import Decimal

def main(arr, n, m):
	idx = [[0 for i in range(n + 1)] for j in range(m)]
	if m == 1:
		return n * (n + 1) // 2
	new = True
	l = 0
	for i in range(m):
		for j in range(n):
			idx[i][arr[i][j]] = j
	curr_idx = [0] * m
	ans = 0
	i = 0
	while i < len(arr[0]):
		val = arr[0][i]
		if new:
			new = False
			for j in range(m):
				curr_idx[j] = idx[j][val]
			l = 1
		else:
			for j in range(m):
				if idx[j][val] != curr_idx[j] + 1:
					ans += l * (l + 1) // 2
					new = True
					i -= 1
					break
				else:
					curr_idx[j] += 1
			if not new:
				l += 1
		i += 1
	if l >= 1:
		ans += l * (l + 1) // 2
	return ans
(n, m) = list(map(int, input().split()))
arr = []
for i in range(m):
	arr.append(list(map(int, input().split())))
print(main(arr, n, m))


(n, m) = map(int, input().split())
before = [None] + [-1] * n
after = [None] + [-1] * n
for i in range(m):
	l = list(map(int, input().split()))
	before[l[0]] = False
	after[l[-1]] = False
	for i in range(n - 1):
		if after[l[i]] == -1:
			after[l[i]] = l[i + 1]
		elif after[l[i]] != l[i + 1]:
			after[l[i]] = False
		if before[l[i + 1]] == -1:
			before[l[i + 1]] = l[i]
		elif before[l[i + 1]] != l[i]:
			before[l[i + 1]] = False
seen = [None] + [0] * n
tot = 0
for i in range(1, n + 1):
	if seen[i] == 0:
		start = i
		end = i
		leng = 1
		seen[i] = 1
		while True:
			if type(after[end]) == int:
				leng += 1
				end = after[end]
				seen[end] = 1
			else:
				break
		while True:
			if type(before[start]) == int:
				leng += 1
				start = before[start]
				seen[start] = 1
			else:
				break
		tot += leng * (leng + 1) // 2
print(tot)


I = lambda : map(int, input().split())
(n, m) = I()
a = [[]] * 10
indexwaliarray = [[0 for i in range(n)] for _ in range(m)]
for i in range(m):
	a[i] = list(I())
for i in range(m):
	for j in range(n):
		indexwaliarray[i][a[i][j] - 1] = j
answaliarray = [[a[0][i] - 1, a[0][i + 1] - 1] for i in range(n - 1)]
for i in range(n - 1):
	for j in range(1, m):
		if indexwaliarray[j][answaliarray[i][1]] != indexwaliarray[j][answaliarray[i][0]] + 1:
			answaliarray[i] = [-1, -1]
count = []
c = 0
for i in range(n - 1):
	if answaliarray[i] == [-1, -1]:
		if c != 0:
			count.append(c)
			c = 0
	else:
		c += 1
if c != 0:
	count.append(c)
yepakkaanshai = 0
for i in count:
	yepakkaanshai += (i + 1) * i // 2
print(yepakkaanshai + n)


def summarize(val):
	return (val + 1) * val // 2

def calc(data):
	m = len(data)
	n = len(data[0])
	reflections = []
	for i in range(m):
		reflections.append(dict())
		r = reflections[-1]
		for j in range(n):
			r[data[i][j]] = j
	lengths = []
	index = 0
	while index < n:
		val = data[0][index]
		ln = 1
		indexes = [reflections[i][val] for i in range(1, m)]
		for k in range(index + 1, n):
			d = k - index
			equal = True
			val = data[0][k]
			for i in range(1, m):
				if indexes[i - 1] + d >= n or data[i][indexes[i - 1] + d] != val:
					equal = False
					break
			if equal:
				ln += 1
			else:
				break
		lengths.append(summarize(ln))
		index += ln
	return sum(lengths)

def get_ints():
	return [int(n) for n in input().split()]

def get_floats():
	return [float(n) for n in input().split()]

def seq2str(seq):
	return ' '.join((str(item) for item in seq))

def __starting_point():
	a = get_ints()
	assert len(a) == 2
	(n, m) = (a[0], a[1])
	data = []
	for i in range(m):
		a = get_ints()
		assert len(a) == n
		data.append(a)
	res = calc(data)
	print(res)
__starting_point()


def intersection(a, b):
	ret = (max(a[0], b[0]), min(a[1], b[1]))
	if ret[0] >= ret[1]:
		return (-1, -1)
	return ret

def calc(n, m, interval):
	ret = 0
	it_list = [(0, n - 1)]
	for i in range(m):
		interval_now = interval[i]
		if len(interval_now) == 0:
			return 0
		next_list = []
		j = 0
		k = 0
		while j < len(it_list) and k < len(interval_now):
			n1 = it_list[j]
			n2 = interval_now[k]
			inter = intersection(n1, n2)
			if inter[0] == -1:
				if n1[0] < n2[0]:
					j += 1
				else:
					k += 1
				continue
			next_list.append(inter)
			if n1[1] < n2[1]:
				j += 1
			else:
				k += 1
		it_list = next_list
		if len(it_list) == 0:
			return 0
	for it in it_list:
		l = it[1] - it[0] + 1
		ret += l * (l + 1) // 2 - l
	return ret

def main():
	(n, m) = map(lambda x: int(x), input().split(' '))
	a = []
	for i in range(m):
		now = list(map(lambda x: int(x), input().split(' ')))
		a.append(now)
	ans = n
	if m == 1:
		print(n * (n + 1) // 2)
		return
	ch = [0 for i in range(n)]
	for i in range(n):
		ch[a[0][i] - 1] = i
	for i in range(m):
		for j in range(n):
			a[i][j] = ch[a[i][j] - 1]
	interval = []
	for i in range(m):
		a_now = a[i]
		l = 0
		r = 0
		now = []
		for j in range(1, n):
			if a_now[j] == a_now[j - 1] + 1:
				r += 1
			else:
				if r > l:
					it = (a_now[l], a_now[r])
					now.append(it)
				l = j
				r = j
		if r > l:
			it = (a_now[l], a_now[r])
			now.append(it)
		now = sorted(now, key=lambda x: x[0])
		interval.append(now)
	ans += calc(n, m, interval)
	print(ans)
main()


(n, m) = map(int, input().split())
graph = [0] * n
_next = [True] * n
_next[n - 1] = False

def read_array():
	return list(map(lambda x: x - 1, map(int, input().split())))
first = read_array()
for i in range(n):
	graph[first[i]] = i
for cnt in range(1, m):
	a = read_array()
	for i in range(n - 1):
		if graph[a[i]] + 1 != graph[a[i + 1]]:
			_next[graph[a[i]]] = False
	_next[graph[a[n - 1]]] = False
l = 0
ans = 0
for cnt in range(n):
	l += 1
	if not _next[cnt]:
		ans += l * (l + 1) // 2
		l = 0
print(ans)


def main():
	(n, m) = [int(c) for c in input().split()]
	if m == 1:
		print(n * (n + 1) // 2)
		return
	testimonies = [[int(c) for c in input().split()] for _ in range(m)]
	perm_map = {client: i for (i, client) in enumerate(testimonies[0])}
	testimonies = [[perm_map[client] for client in testimonies[i]] for i in range(1, m)]
	counters = []
	for t in testimonies:
		seq_map = [0] * n
		(start, i) = (0, 1)
		seq_map[t[start]] = 1
		while i < len(t):
			if t[i] - t[i - 1] == 1:
				seq_map[t[start]] += 1
			else:
				cnt = seq_map[t[start]]
				for j in range(start + 1, i):
					cnt -= 1
					seq_map[t[j]] = cnt
				start = i
				seq_map[t[start]] = 1
			i += 1
		cnt = seq_map[t[start]]
		for j in range(start + 1, i):
			cnt -= 1
			seq_map[t[j]] = cnt
		counters.append(seq_map)
	ans = sum([min([cnt[i] for cnt in counters]) for i in range(n)])
	print(ans)
main()


(n, m) = map(int, input().split())
arr = []
arr1 = []
for i in range(m):
	arrx = list(map(int, input().split()))
	arry = [0] * n
	for j in range(n):
		arry[arrx[j] - 1] = j + 1
	arr.append(arrx)
	arr1.append(arry)
ans = n
i = 0
j = 1
flag = 0
while i < n - 1 and j < n:
	k1 = arr[0][i]
	k2 = arr[0][j]
	l = 0
	while l < m:
		if arr1[l][arr[0][j - 1] - 1] != arr1[l][arr[0][j] - 1] - 1:
			flag = 1
			break
		if flag == 1:
			break
		l += 1
	if flag == 1:
		ans += (j - i) * (j - i + 1) // 2
		ans -= j - i
		i = j
		j += 1
		flag = 0
	else:
		j += 1
if flag == 0:
	ans += (j - i) * (j - i + 1) // 2
	ans -= j - i
print(ans)


(n, m) = map(int, input().split())
a = []
pos = [[0] * n for _ in range(m)]
for i in range(m):
	tmp = [x - 1 for x in map(int, input().split())]
	a.append(tmp)
	for (j, x) in enumerate(tmp):
		pos[i][x] = j
prev = [-1] * m
ans = 0
cnt = 0
for i in range(n):
	v = a[0][i]
	if all((pos[j][v] == prev[j] + 1 or prev[j] == -1 for j in range(m))):
		cnt += 1
	else:
		cnt = 1
	ans += cnt
	prev = [pos[j][v] for j in range(m)]
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, m) = map(int, input().split())
(a, d) = ([], [])
for _ in range(m):
	b = [*map(int, input().split())]
	e = {}
	for i in range(n):
		e[b[i]] = i
	d.append(e)
	a.append(b)
if m == 1:
	ans = n * (n + 1) // 2
else:
	ans = 0
if m > 1:
	i = 0
	while i < n:
		l = float('inf')
		for x in range(1, m):
			(j, k, ll) = (d[x][a[0][i]], i, 0)
			while j < n and k < n and (a[x][j] == a[0][k]):
				k += 1
				j += 1
				ll += 1
			l = min(l, ll)
		ans += l * (l + 1) // 2
		i += l
print(ans)


(n, k) = map(int, input().split())
entry = list(map(int, input().split()))
pos = dict()
stop = {entry[-1]}
for (idx, v) in enumerate(entry):
	pos[v] = idx
for i in range(k - 1):
	(tmp, override) = (list(map(int, input().split())), list())
	tmpIdx = 0
	while tmpIdx < n:
		entryIdx = pos[tmp[tmpIdx]]
		processed = False
		while tmpIdx < n and entryIdx < n and (tmp[tmpIdx] == entry[entryIdx]):
			tmpIdx += 1
			entryIdx += 1
			processed = True
			if tmp[tmpIdx - 1] in stop:
				break
		stop.add(tmp[tmpIdx - 1])
		if not processed:
			tmpIdx += 1
cnt = 1
ans = 0
for v in entry:
	if v in stop:
		ans += cnt * (cnt + 1) // 2
		cnt = 1
	else:
		cnt += 1
print(ans)


(n, m) = [int(i) for i in input().split(' ')]
import sys
fconnection = [None] * n
bconnection = [None] * n
if m == 1:
	print(int((n + 1) * n / 2))
	return
svidetel = input().split(' ')
p = int(svidetel[0]) - 1
for current_pok in svidetel[1:]:
	q = int(current_pok) - 1
	fconnection[p] = q
	bconnection[q] = p
	p = q
for i in range(m - 1):
	svidetel = input().split(' ')
	p = int(svidetel[0]) - 1
	bconnection[p] = None
	for current_pok in svidetel[1:]:
		q = int(current_pok) - 1
		if fconnection[p] != q:
			fconnection[p] = None
		if bconnection[q] != p:
			bconnection[q] = None
		p = q
	fconnection[p] = None
is_bundled = [True] + [False] * (n - 1)
unbundled_count = n
current_bundle = []
number_of_variants = 0
research_deck = [0]
for i in range(n):
	if fconnection[i] == None and bconnection[i] == None:
		number_of_variants += 1
	elif bconnection[i] == None:
		number_in_run = 1
		next_in_run = fconnection[i]
		while next_in_run is not None:
			number_in_run += 1
			next_in_run = fconnection[next_in_run]
		number_of_variants += int((1 + number_in_run) * number_in_run / 2)
print(number_of_variants)


from sys import stdin
(n, m) = map(int, stdin.readline().strip().split())
dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]
for i in range(m):
	s = list(map(int, stdin.readline().strip().split()))
	for j in range(n - 2, -1, -1):
		dp[i][s[j]] = s[j + 1]
dp1 = [1 for i in range(n)]
for i in range(n - 2, -1, -1):
	t = True
	for j in range(m):
		if dp[j][s[i]] != s[i + 1]:
			t = False
	if t:
		dp1[i] = dp1[i] + dp1[i + 1]
print(sum(dp1))


def find(x):
	if par[x] == x:
		return par[x]
	par[x] = find(par[x])
	return par[x]

def union(a, b):
	pa = find(a)
	pb = find(b)
	if pa != pb:
		if size[pa] > size[pb]:
			(pa, pb) = (pb, pa)
		size[pb] += size[pa]
		size[pa] = 1
		par[pa] = pb
(n, m) = map(int, input().split())
b = []
par = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
for i in range(m):
	arr = list(map(int, input().split()))
	b.append(arr)
collect = []
d = {}
e = {}
for i in range(m):
	e = {}
	for j in range(n - 1):
		if i == 0:
			d[b[i][j]] = b[i][j + 1]
		elif b[i][j] in d and d[b[i][j]] == b[i][j + 1]:
			e[b[i][j]] = b[i][j + 1]
	if i > 0:
		d = e
count = 0
for i in range(n):
	if i + 1 in d:
		union(i + 1, d[i + 1])
ans = 0
count = n
for i in range(1, n + 1):
	if size[i] > 1:
		ans += size[i] * (size[i] + 1) // 2
		count -= size[i]
print(ans + count)


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
(n, k) = map(int, input().split())
entry = list(map(int, input().split()))
pos = dict()
stop = {entry[-1]}
for (idx, v) in enumerate(entry):
	pos[v] = idx
for i in range(k - 1):
	(tmp, override) = (list(map(int, input().split())), list())
	tmpIdx = 0
	while tmpIdx < n:
		entryIdx = pos[tmp[tmpIdx]]
		processed = False
		while tmpIdx < n and entryIdx < n and (tmp[tmpIdx] == entry[entryIdx]):
			tmpIdx += 1
			entryIdx += 1
			processed = True
			if tmp[tmpIdx - 1] in stop:
				break
		stop.add(tmp[tmpIdx - 1])
		if not processed:
			tmpIdx += 1
cnt = 1
ans = 0
for v in entry:
	if v in stop:
		ans += cnt * (cnt + 1) // 2
		cnt = 1
	else:
		cnt += 1
print(ans)


(n, m) = map(int, input().split())
lis = []
for i in range(m):
	li = [0] + list(map(int, input().split()))
	lis.append(li)
ren = [0] * (n + 1)
for i in range(1, n + 1):
	ren[lis[0][i]] = i
for i in range(m):
	for j in range(1, n + 1):
		lis[i][j] = ren[lis[i][j]]
ans = [[0] * (n + 1) for i in range(m)]
for _ in range(m):
	i = 1
	while i <= n:
		j = i
		while j < n and lis[_][j] + 1 == lis[_][j + 1]:
			j += 1
		for k in range(i, j + 1):
			ans[_][lis[_][k]] = j - k + 1
		i = j + 1
aa = 0
for i in range(1, n + 1):
	mi = 1000000000000000
	for j in range(m):
		mi = min(mi, ans[j][i])
	aa += mi
print(aa)


import os
from io import BytesIO
if os.name == 'nt':
	input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	(n, m) = map(int, input().split())
	l = []
	inv = []
	for i in range(m):
		per = list(map(int, input().split()))
		invper = [0] * (n + 1)
		for (nr, x) in enumerate(per):
			invper[x] = nr
		l.append(per)
		inv.append(invper)
	curpos = [None] * m
	curlen = 0
	res = 0
	for x in l[0]:
		for i in range(0, m):
			if curpos[i] != None and inv[i][x] != curpos[i] + 1:
				res += curlen * (curlen + 1) // 2
				curlen = 0
			curpos[i] = inv[i][x]
		curlen += 1
	res += curlen * (curlen + 1) // 2
	print(res)
main()


from sys import stdin, stdout
from math import floor

def main():
	global n, m, a
	(n, m) = [int(x) for x in stdin.readline().split()]
	a = []
	for i in range(m):
		a.append([int(x) for x in stdin.readline().split()])
	g = []
	G = []
	for i in range(n + 3):
		g.append({})
		G.append({})
	for j in range(m):
		b = a[j]
		for i in range(1, n):
			u = b[i - 1]
			v = b[i]
			if g[u].get(v) == None:
				g[u][v] = 1
			else:
				g[u][v] = g[u][v] + 1
	for u in range(1, n + 1):
		for (v, k) in g[u].items():
			if k == m:
				G[u][v] = True
	res = 0
	i = 0
	j = -1
	b = a[0] + [0]
	res = 0
	while i < n and j < n:
		i = j + 1
		j = j + 1
		if i >= n or j >= n:
			break
		while j + 1 < n:
			if G[b[j]].get(b[j + 1]) == True:
				j = j + 1
			else:
				break
		l = j - i + 1
		res = res + l + floor(l * (l - 1) / 2)
	stdout.write(str(res))
	return 0
main()


(n, m) = map(int, input().split())
if m == 1:
	ar = list(map(int, input().split()))
	print(n * (n + 1) // 2)
	exit()
ar = list(map(int, input().split()))
dd = dict(zip(zip(ar, ar[1:]), [1] * (n - 1)))
for v in range(m - 2):
	ar = list(map(int, input().split()))
	a = ar[0]
	for i in range(1, n):
		b = ar[i]
		if (a, b) in dd:
			dd[a, b] += 1
		a = b
m -= 1
ar = list(map(int, input().split()))
a = ar[0]
bo = False
l = 2
s = 0
for i in range(1, n):
	b = ar[i]
	if (a, b) in dd and dd[a, b] == m:
		if bo:
			if y == a:
				l += 1
				y = b
			else:
				s += l * (l - 1) // 2
				l = 2
				x = a
				y = b
		else:
			(x, y) = (a, b)
			bo = True
	a = b
if bo:
	s += l * (l - 1) // 2
print(n + s)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from sys import stdin
(n, m) = map(int, stdin.readline().strip().split())
dp = [[-1 for i in range(n + 1)] for j in range(m + 1)]
for i in range(m):
	s = list(map(int, stdin.readline().strip().split()))
	for j in range(n - 2, -1, -1):
		dp[i][s[j]] = s[j + 1]
dp1 = [1 for i in range(n)]
for i in range(n - 2, -1, -1):
	t = True
	for j in range(m):
		if dp[j][s[i]] != s[i + 1]:
			t = False
	if t:
		dp1[i] = dp1[i] + dp1[i + 1]
print(sum(dp1))


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve():
	(n, m) = li()
	da = [defaultdict(lambda : 0) for i in range(m)]
	a = []
	for i in range(m):
		l = li()
		a.append(l)
		for j in range(n):
			da[i][l[j]] = j
	ans = []
	cur = 0
	prev = -1
	for i in range(n):
		x = l[i]
		if prev == -1:
			prev = x
			cur = 1
		else:
			flag = 0
			for j in range(m):
				indofx = da[j][x]
				if indofx > 0:
					if a[j][indofx - 1] == prev:
						continue
					else:
						flag = 1
						break
				else:
					flag = 1
					break
			if flag == 1:
				ans.append(cur)
				cur = 1
				prev = x
			else:
				cur += 1
				prev = x
	if cur > 0:
		ans.append(cur)
	res = 0
	for i in ans:
		res += i * (i + 1) // 2
	print(res)
t = 1
for _ in range(t):
	solve()


(n, m) = map(int, input().split())
from collections import *
al = defaultdict(list)
for i in range(m):
	z = list(map(int, input().split()))
	for i in range(len(z)):
		al[z[i]].append(i)
dl = defaultdict(int)
total = 0
for i in range(len(z)):
	count = 1
	x = z[i]
	if dl[x] == 1:
		continue
	dl[x] = 1
	q = al[x]
	total += count
	start = 1
	count += 1
	while 1:
		for i in range(len(q)):
			q[i] += start
		s = []
		u = q[-1]
		if u < len(z):
			s = al[z[u]]
			if s == q:
				total += count
				count += 1
				dl[z[u]] = 1
			else:
				break
		else:
			break
print(total)


def intersect(seqOne, seqTwo):
	seqOne = sorted(seqOne, key=lambda x: x[0])
	seqTwo = sorted(seqTwo, key=lambda x: x[0])
	i = 0
	j = 0
	ans = []
	while i < len(seqOne) and j < len(seqTwo):
		(a, b) = seqOne[i]
		(c, d) = seqTwo[j]
		if max(a, c) < min(b, d):
			ans.append((max(a, c), min(b, d)))
		if b < d:
			i += 1
		else:
			j += 1
	return ans

def main():
	(n, m) = map(int, input().strip().split())
	orders = []
	for i in range(m):
		orders.append([int(x) for x in input().strip().split()])
	ind = [0] * (n + 1)
	for i in range(1, n + 1):
		ind[orders[0][i - 1]] = i
	subseqs = [(1, n)]
	for i in range(1, m):
		order = list(map(lambda x: ind[x], orders[i]))
		i = 0
		currSubseqs = []
		for j in range(1, n):
			if order[j] == order[j - 1] + 1:
				continue
			else:
				if j - i > 1:
					currSubseqs.append((order[i], order[j - 1]))
				i = j
		if i != n - 1:
			currSubseqs.append((order[i], order[j]))
		subseqs = intersect(subseqs, currSubseqs)
		if len(subseqs) == 0:
			break
	ans = n
	for subseq in subseqs:
		(x, y) = subseq
		m = y - x + 1
		ans += m * (m + 1) // 2 - m
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
g = [0] * n
nxt = [True] * n
nxt[-1] = False

def read_array():
	return list(map(lambda x: x - 1, map(int, input().split())))
f = read_array()
for i in range(n):
	g[f[i]] = i
for _ in range(1, m):
	a = read_array()
	for i in range(n - 1):
		if g[a[i]] + 1 != g[a[i + 1]]:
			nxt[g[a[i]]] = False
	nxt[g[a[n - 1]]] = False
(l, ans) = (0, 0)
for i in range(n):
	l += 1
	if not nxt[i]:
		ans += l * (l + 1) // 2
		l = 0
print(ans)


from collections import defaultdict
from collections import deque
(n, m) = [int(x) for x in input().split()]
messages = []
for i in range(m):
	temp = [int(x) for x in input().split()]
	messages.append(temp)
seq = defaultdict(lambda : 0)
pairs = {}
for k in range(n - 1):
	pairs[messages[0][k]] = messages[0][k + 1]
for i in range(1, m):
	for k in range(n - 1):
		temp = messages[i][k]
		if pairs.get(temp, None) != messages[i][k + 1]:
			pairs.pop(temp, None)
	pairs.pop(messages[i][n - 1], None)
sequences = []
starts = set(pairs.keys())
ends = set(pairs.values())
conn = starts & ends
for (key, value) in list(pairs.items()):
	if key in conn:
		continue
	val = value
	temp = []
	temp.append(key)
	temp.append(value)
	while val in starts:
		val = pairs[val]
		temp.append(val)
	sequences.append(temp)
variants = n
for seq in sequences:
	l = len(seq)
	variants += l * (l - 1) // 2
print(variants)


from sys import stdin, stdout
(n, m) = [int(x) for x in stdin.readline().split()]
n += 1
a = [[-1] + [int(x) for x in stdin.readline().split()] for _ in range(m)]
idx = [[-1] * n for _ in range(m)]
for mi in range(m):
	for ni in range(1, n):
		x = a[mi][ni]
		idx[mi][x] = ni
sz = 1
sols = 0
for ni in range(2, n):
	prev = a[0][ni - 1]
	curr = a[0][ni]
	for mi in range(1, m):
		xi = idx[mi][prev] + 1
		yi = idx[mi][curr]
		if xi != yi:
			sols += sz * (sz + 1) // 2
			sz = 0
			break
	sz += 1
sols += sz * (sz + 1) // 2
stdout.write('{}\n'.format(sols))


def main():
	(N, M) = [int(x) for x in input().split()]
	arrs = []
	for _ in range(M):
		arrs.append([int(x) - 1 for x in input().split()])
	print(solve(N, M, arrs))

def solve(N, M, arrs):
	next_arr = [None] * N
	arr = arrs[0]
	for (r, nr) in zip(arr, arr[1:]):
		next_arr[r] = nr
	for i in range(1, M):
		read = arrs[i]
		next_arr_new = [None] * N
		for (r, nr) in zip(read, read[1:]):
			next_arr_new[r] = nr
		for (r, nr) in enumerate(next_arr_new):
			if next_arr[r] != nr:
				next_arr[r] = None
	starts = []
	cycs = []
	curr = 0
	for r in arr:
		if next_arr[r] != None:
			if curr == 0:
				starts.append(r)
			curr += 1
		elif curr > 0:
			cycs.append(curr)
			curr = 0
	if curr > 0:
		cycs.append(curr)
	assert len(starts) == len(cycs)
	s = 0
	for c in cycs:
		s += c * (c + 1) // 2
	s += N
	return s
solve(3, 2, [[0, 1, 2], [0, 1, 2]])

def solve_naive(r1, r2):
	count = 0
	for i in range(len(r1)):
		for j in range(i + 1, len(r1) + 1):
			for ii in range(len(r2)):
				l = j - i
				if r1[i:j] == r2[ii:ii + l]:
					count += 1
	return count

def test(N):
	from random import shuffle
	for i in range(1000):
		r1 = list(range(N))
		r2 = list(range(N))
		shuffle(r1)
		shuffle(r2)
		res = solve(N, 2, [r1, r2])
		res2 = solve_naive(r1, r2)
		if res != res2:
			print(r1, r2)
			print(res, res2)
			assert res == res2
main()


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, file=sys.stderr)
	dprint('debug mode')
except Exception:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N, M) = getIntList()
ne = [0 for i in range(N + 1)]
za = getIntList()
for i in range(N - 1):
	ne[za[i]] = za[i + 1]
ne[za[-1]] = 0
for _ in range(1, M):
	za = getIntList()
	for i in range(N - 1):
		a = za[i]
		b = za[i + 1]
		if ne[a] != b:
			ne[a] = -1
	a = za[-1]
	if ne[a] != 0:
		ne[a] = -1
tin = [0 for i in range(N + 1)]
for i in range(1, N + 1):
	a = ne[i]
	if a > 0:
		tin[a] = 1
res = 0
for i in range(1, N + 1):
	if tin[i]:
		continue
	n = 0
	while i > 0:
		n += 1
		i = ne[i]
	res += n * (n + 1) // 2
print(res)


import sys
a = []
(n, m) = map(int, sys.stdin.readline().strip().split())
b = [[-1 for i in range(n + 1)] for j in range(m + 1)]
for f in range(m):
	a = list(map(int, sys.stdin.readline().strip().split()))
	for k in range(n - 2, -1, -1):
		b[f][a[k]] = a[k + 1]
c = [1 for i in range(n)]
for g in range(n - 2, -1, -1):
	d = True
	for v in range(m):
		if b[v][a[g]] != a[g + 1]:
			d = False
	if d:
		c[g] = c[g] + c[g + 1]
print(sum(c))


from math import inf as inf
from math import *
from collections import *
import sys
input = sys.stdin.readline
t = 1
while t:
	t -= 1
	(n, m) = map(int, input().split())
	ind = [0 for i in range(n)]
	vis = [1 for i in range(n)]
	vis[-1] = 0
	a = list(map(int, input().split()))
	for i in range(n):
		ind[a[i] - 1] = i
	for i in range(m - 1):
		a = list(map(int, input().split()))
		for j in range(n - 1):
			if ind[a[j] - 1] + 1 == ind[a[j + 1] - 1]:
				continue
			vis[ind[a[j] - 1]] = 0
		vis[ind[a[n - 1] - 1]] = 0
	r = 0
	c = 0
	for i in vis:
		c += 1
		if i == 0:
			r += c * (c + 1) // 2
			c = 0
	print(r)


from sys import stdin, stdout
from math import sqrt
import math
import heapq
from itertools import accumulate
(N, M) = [int(x) for x in stdin.readline().split()]
res = 0
data = []
order = [[0] * N for _ in range(M)]
for i in range(M):
	arr = [int(x) for x in stdin.readline().split()]
	if i == 0:
		data = list(arr)
	else:
		for j in range(N):
			order[i][arr[j] - 1] = j
tmp = []
neigbor = [0] * M
L = 0
for i in range(N):
	num = data[i]
	L += 1
	flag = 0
	for j in range(1, M):
		pos = order[j][num - 1]
		if pos != neigbor[j] + 1:
			flag = 1
		neigbor[j] = pos
	if i == 0:
		flag = 0
	if flag == 1:
		L -= 1
		res += (L + 1) * L // 2
		L = 1
res += (L + 1) * L // 2
print(res)


(n, m) = map(int, input().split())
l = [[0] * (n + 1) for i in range(m)]
pos = [[0] * (n + 1) for i in range(m)]
dp = [0 for i in range(n + 1)]
for i in range(m):
	k = 0
	for j in list(map(int, input().split())):
		l[i][k] = j
		pos[i][j] = k
		k += 1
ans = n
for i in range(n - 2, -1, -1):
	val = l[0][i]
	value = 0
	for j in range(m):
		if l[j][pos[j][val] + 1] == l[0][i + 1]:
			value += 1
	if value == m:
		dp[i] += dp[i + 1] + 1
	ans += dp[i]
print(ans)


(n, m) = map(int, input().split())
a = []
for i in range(m):
	a.append(list(map(int, input().split())))
b = [set([]) for i in range(n)]
for i in range(n):
	for j in range(m):
		ya = a[j][i]
		if i == n - 1:
			b[ya - 1].add(100000000)
		else:
			b[ya - 1].add(a[j][i + 1])

class UnionFind:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] != self.table[s2]:
				if self.table[s1] < self.table[s2]:
					self.table[s2] = s1
				else:
					self.table[s1] = s2
			else:
				self.table[s1] += -1
				self.table[s2] = s1
		return
UN = UnionFind(n)
for i in range(n):
	if len(b[i]) == 1 and list(b[i])[0] != 100000000:
		UN.union(i, list(b[i])[0] - 1)
d = [0] * n
for i in range(n):
	d[UN.find(i)] += 1
ans = 0
for i in range(n):
	ans += (d[i] - 1) * d[i] // 2
print(ans + n)