You're given an undirected graph with $n$ nodes and $m$ edges. Nodes are numbered from $1$ to $n$.

The graph is considered harmonious if and only if the following property holds:  For every triple of integers $(l, m, r)$ such that $1 \le l < m < r \le n$, if there exists a path going from node $l$ to node $r$, then there exists a path going from node $l$ to node $m$. 

In other words, in a harmonious graph, if from a node $l$ we can reach a node $r$ through edges ($l < r$), then we should able to reach nodes $(l+1), (l+2), \ldots, (r-1)$ too.

What is the minimum number of edges we need to add to make the graph harmonious? 


-----Input-----

The first line contains two integers $n$ and $m$ ($3 \le n \le 200\ 000$ and $1 \le m \le 200\ 000$).

The $i$-th of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), that mean that there's an edge between nodes $u$ and $v$.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).


-----Output-----

Print the minimum number of edges we have to add to the graph to make it harmonious.


-----Examples-----
Input
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12

Output
1

Input
200000 3
7 9
9 8
4 5

Output
0



-----Note-----

In the first example, the given graph is not harmonious (for instance, $1 < 6 < 7$, node $1$ can reach node $7$ through the path $1 \rightarrow 2 \rightarrow 7$, but node $1$ can't reach node $6$). However adding the edge $(2, 4)$ is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Sorting

Greedy algorithms

Spanning trees
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
global par, sz, mx

def find(u):
	global par, sz, mx
	if par[u] == u:
		return u
	return find(par[u])

def unite(u, v):
	global par, sz, mx
	p1 = find(u)
	p2 = find(v)
	if p1 == p2:
		return
	if sz[p1] < sz[p2]:
		(p1, p2) = (p2, p1)
	sz[p1] += sz[p2]
	mx[p1] = max(mx[p1], mx[p2])
	par[p2] = p1
(n, m) = map(int, sys.stdin.readline().split())
par = [i for i in range(n)]
mx = [i for i in range(n)]
sz = [1] * n
for _ in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	u -= 1
	v -= 1
	unite(u, v)
comp = 0
mxb = 0
for i in range(n):
	if find(i) == i:
		comp += 1
for i in range(n):
	mxb = max(mxb, mx[find(i)])
	if mxb == i:
		comp -= 1
print(comp)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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 collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 10 ** 9 + 7

def solve():
	(N, M) = getInts()
	graph = dd(set)
	for m in range(M):
		(U, V) = getInts()
		U -= 1
		V -= 1
		graph[U].add(V)
		graph[V].add(U)
	global max_visited
	max_visited = -1
	used = set()
	nodes = [j for j in range(N - 1, -1, -1)]

	def dfs(node):
		global max_visited
		used.add(node)
		max_visited = max(max_visited, node)
		queue = [node]
		while queue:
			node = queue.pop()
			for neigh in graph[node]:
				if neigh not in used:
					used.add(neigh)
					max_visited = max(max_visited, neigh)
					queue.append(neigh)
		return
	ans = 0
	while nodes:
		node = nodes.pop()
		if node in used:
			continue
		if node < max_visited:
			ans += 1
		dfs(node)
	return ans
print(solve())


import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

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

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

	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.parents) if x < 0]

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

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
(n, m) = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
	(u, v) = map(int, input().split())
	uf.union(u - 1, v - 1)
MIN = [i for i in range(n)]
for i in range(n):
	MIN[uf.find(i)] = min(i, MIN[uf.find(i)])
ans = 0
min_i = n - 1
for i in range(n)[::-1]:
	if min_i < MIN[uf.find(i)]:
		MIN[uf.find(i)] = min(MIN[uf.find(i)], MIN[uf.find(min_i)])
		ans += 1
		uf.union(i, min_i)
	else:
		min_i = MIN[uf.find(i)]
print(ans)


import sys
inp = sys.stdin.readlines()
(n, m) = [int(i) for i in inp[0].split()]
d = [[] for i in range(n + 1)]
for j in range(1, m + 1):
	(a, b) = [int(i) for i in inp[j].split()]
	d[a].append(b)
	d[b].append(a)
fnd = [0] * (n + 1)
comps = []
for i in range(1, n + 1):
	if not fnd[i]:
		comp = [i]
		fnd[i] = 1
		st = [i]
		while st:
			v = st.pop()
			for vv in d[v]:
				if not fnd[vv]:
					fnd[vv] = 1
					st.append(vv)
					comp.append(vv)
		comps.append((min(comp), max(comp)))
comps.sort()
cnt = 1
ub = comps[0][1]
for cp in comps:
	if cp[0] > ub:
		cnt += 1
	ub = max(ub, cp[1])
print(len(comps) - cnt)


import sys
import collections
(n, m) = [int(x) for x in sys.stdin.readline().split(' ')]
adj = collections.defaultdict(list)
vis = [0] * (n + 1)
for i in range(m):
	(u, v) = [int(x) for x in sys.stdin.readline().split(' ')]
	adj[u].append(v)
	adj[v].append(u)
maxu = -1
ans = 0
for i in range(1, n + 1):
	if not vis[i]:
		if i < maxu:
			ans += 1
		s = [i]
		while len(s) > 0:
			u = s.pop()
			maxu = max(u, maxu)
			vis[u] = True
			for v in adj[u]:
				if not vis[v]:
					s.append(v)
					vis[v] = True
print(ans)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1
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

class DSU:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.rank = [0 for i in range(n + 1)]

	@bootstrap
	def find_set(self, v):
		if v == self.parent[v]:
			yield v
		self.parent[v] = (yield self.find_set(self.parent[v]))
		yield self.parent[v]

	def union(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		if a != b:
			if a < b:
				(a, b) = (b, a)
			self.parent[b] = a
			if self.rank[a] == self.rank[b]:
				self.rank[a] += 1

def main():
	try:
		(n, m) = In()
		dsu = DSU(n)
		for i in range(m):
			(a, b) = In()
			dsu.union(a, b)
		d = defaultdict(list)
		i = 1
		cnt = 0
		while i <= n:
			mx = dsu.find_set(i)
			while i <= mx:
				if dsu.find_set(i) != mx:
					temp = dsu.find_set(i)
					dsu.union(temp, mx)
					mx = max(temp, mx)
					cnt += 1
				i += 1
		print(cnt)
	except RuntimeError as e:
		print(e)
M = 998244353
P = 1000000007
for _ in range(1):
	main()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter, defaultdict as dd
import threading
sys.setrecursionlimit(201005)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdarr = lambda : map(int, stdstr().split())
mod = 1000000007

def DFS(graph, node, visited, minim, maxim):
	visited[node - 1] = True
	if node < minim[-1]:
		minim.append(node)
	if node > maxim[-1]:
		maxim.append(node)
	for i in graph[node]:
		if visited[i - 1] == False:
			DFS(graph, i, visited, minim, maxim)

def main():
	(n, m) = stdarr()
	graph = {}
	for i in range(n):
		graph[i + 1] = []
	for i in range(m):
		(a, b) = stdarr()
		graph[a].append(b)
		graph[b].append(a)
	visited = [False] * n
	components = []
	for i in range(n):
		if visited[i] == False:
			minim = [i + 1]
			maxim = [i + 1]
			DFS(graph, i + 1, visited, minim, maxim)
			components.append([minim[-1], maxim[-1]])
	res = 0
	currMax = -1
	for i in range(len(components)):
		if components[i][0] <= currMax:
			res += 1
		currMax = max(currMax, components[i][1])
	print(res)
arr = []
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=main)
thread.start()


def main():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n + 1):
		a.append([])
	for i in range(m):
		(u, v) = map(int, input().split())
		a[u].append(v)
		a[v].append(u)
	used = [0] * (n + 1)
	ans = 0
	con = 1
	for i in range(1, n + 1):
		if not used[i]:
			b = [i]
			if i < con:
				ans += 1
			while len(b):
				tc = b.pop()
				if not used[tc]:
					b += a[tc]
					used[tc] = 1
					if tc > con:
						con = tc
	print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
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 collections import defaultdict, deque
(n, m) = map(int, input().split())
graph = [[] for s in range(n)]
for s in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
ds = {}
vis = set([])
for s in range(n):
	if not s in vis:
		queue = deque([s])
		ds[s] = [[0, 0], set([])]
		minny = 2 * 10 ** 5
		maxy = 0
		while len(queue) > 0:
			v0 = queue.popleft()
			for b in range(len(graph[v0])):
				node = graph[v0][b]
				if not node in vis:
					queue.append(node)
					vis.add(node)
					ds[s][1].add(node)
					maxy = max(node, maxy)
					minny = min(node, minny)
		ds[s][0] = [minny, maxy]
		if len(ds[s][1]) == 0:
			ds.pop(s)
ans = 0
keys = [i for i in ds.keys()]
cur = [ds[keys[0]][0]]
s1 = [ds[keys[0]][1]]
for s in range(1, len(keys)):
	pair = ds[keys[s]][0]
	if pair[0] < cur[-1][1]:
		ans += 1
		cur[-1][1] = max(cur[-1][1], pair[1])
		for i in ds[keys[s]][1]:
			s1[-1].add(i)
	else:
		cur.append(pair)
		s1.append(ds[keys[s]][1])
for s in range(len(cur)):
	ans += cur[s][1] + 1 - cur[s][0] - len(s1[s])
print(ans)


class Input:

	def __init__(self):
		from sys import stdin
		lines = stdin.readlines()
		self.lines = list([line.rstrip('\n') for line in reversed(lines) if line != '\n'])

	def input(self):
		return self.lines.pop()

	def input_int_list(self):
		return list(map(int, self.input().split()))

	def __bool__(self):
		return bool(self.lines)
inp = Input()
(n, m) = inp.input_int_list()
from collections import defaultdict
edge = defaultdict(list)
involved_nodes = set()
not_alone = set()
for __ in range(m):
	(a, b) = inp.input_int_list()
	if a > b:
		(a, b) = (b, a)
	edge[a].append(b)
	edge[b].append(a)
	not_alone.add(a)
	not_alone.add(b)

def bfs(node, visited):
	stack = []
	stack.append(node)
	while stack:
		node = stack.pop()
		visited.add(node)
		for neighbor in edge[node]:
			if neighbor not in visited:
				stack.append(neighbor)

def get_clusters():
	visited = set()
	ranges = []
	for node in range(1, n + 1):
		if node not in not_alone:
			ranges.append((node, node))
		elif node not in visited:
			cluster_visited = set()
			bfs(node, cluster_visited)
			visited.update(cluster_visited)
			ranges.append((min(cluster_visited), max(cluster_visited)))
	return ranges
clusters = get_clusters()
clusters.sort()
total_add = 0
current_group_size = 1
cur_max_group = clusters[0][1]
for (c_min, c_max) in clusters[1:]:
	if c_min <= cur_max_group:
		total_add += 1
	cur_max_group = max(c_max, cur_max_group)
print(total_add)


import sys
from collections import deque

class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int):
		self.nodes = [-1] * n

	def find(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.find(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y, nodes) = (self.find(x), self.find(y), self.nodes)
		if root_x != root_y:
			if nodes[root_x] > nodes[root_y]:
				(root_x, root_y) = (root_y, root_x)
			nodes[root_x] += nodes[root_y]
			nodes[root_y] = root_x
		return root_x != root_y
(n, m) = map(int, input().split())
uf = UnionFind(n)
adj = [[] for _ in range(n)]
for (u, v) in (map(int, sys.stdin.readline().split()) for _ in range(m)):
	u = u - 1
	v = v - 1
	adj[u].append(v)
	adj[v].append(u)
	uf.unite(u, v)
g_range = []
visited = [0] * n
for i in range(n):
	if visited[i] or not adj[i]:
		continue
	dq = deque([i])
	visited[i] = 1
	(min_v, max_v) = (i, i)
	v_set = []
	size = 0
	while dq:
		v = dq.popleft()
		min_v = min(min_v, v)
		max_v = max(max_v, v)
		v_set.append(v)
		size += 1
		for dest in adj[v]:
			if visited[dest]:
				continue
			visited[dest] = 1
			dq.append(dest)
	g_range.append((min_v, max_v))
g_range.sort()
ans = 0
checked_max = 0
for (s, t) in g_range:
	if t <= checked_max:
		continue
	for v in range(max(s, checked_max) + 1, t):
		if uf.unite(s, v):
			ans += 1
	checked_max = max(checked_max, t)
print(ans)


import sys
from collections import defaultdict

def main():
	(n, m) = [int(x) for x in sys.stdin.readline().split(' ')]
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = [int(x) for x in sys.stdin.readline().split(' ')]
		graph[u].append(v)
		graph[v].append(u)
	maxB = -1
	count = 0
	visited = [False for v in range(0, n + 1)]
	stack = []
	for i in range(1, n + 1):
		if visited[i]:
			continue
		if i < maxB:
			count += 1
		stack = [i]
		while len(stack) > 0:
			u = stack.pop()
			for v in graph[u]:
				if v > maxB:
					maxB = v
				if not visited[v]:
					visited[v] = True
					stack.append(v)
	return count
print(main())


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		if Nodes[find(x)] < Nodes[find(y)]:
			Nodes[find(y)] += Nodes[find(x)]
			Nodes[find(x)] = 0
			Group[find(x)] = find(y)
		else:
			Nodes[find(x)] += Nodes[find(y)]
			Nodes[find(y)] = 0
			Group[find(y)] = find(x)
for i in range(m):
	(x, y) = map(int, input().split())
	Union(x, y)
MINI = [i for i in range(n + 1)]
for i in range(n + 1):
	MINI[find(i)] = min(MINI[find(i)], i)
ANS = 0
MIN = n
ANS = 0
for i in range(n, 0, -1):
	if MIN < MINI[find(i)]:
		MINI[find(i)] = min(MINI[find(i)], MINI[find(MIN)])
		Union(MIN, i)
		ANS += 1
	else:
		MIN = MINI[find(i)]
print(ANS)


import sys
from collections import defaultdict

def dfs(s, compN):
	visited[s] = compN
	queue = set(adj[s])
	maxV = s
	while queue:
		v = queue.pop()
		if not visited[v]:
			visited[v] = compN
			maxV = max(maxV, v)
			queue.update(adj[v])
	return maxV

def countEdges(adj, n, m):
	compN = 0
	comps = []
	for s in range(1, n + 1):
		if not visited[s]:
			compN += 1
			minV = s
			maxV = dfs(s, compN)
			comps.append((minV, compN, 0))
			comps.append((maxV, compN, 1))
	comps.sort()
	opened = set()
	ctr = 0
	for (v, compN, closed) in comps:
		if closed:
			opened.remove(compN)
		else:
			if opened:
				ctr += 1
			opened.add(compN)
	return ctr
reader = (map(int, s.split()) for s in sys.stdin)
(n, m) = next(reader)
adj = defaultdict(list)
for _ in range(m):
	(i, j) = next(reader)
	adj[i].append(j)
	adj[j].append(i)
visited = [False] * (n + 1)
ans = countEdges(adj, n, m)
print(ans)


import sys
input = sys.stdin.readline

def root(k):
	while k != l[k]:
		k = l[l[k]]
	return k
(n, m) = map(int, input().split())
l = [i for i in range(n + 1)]
sz = [1] * (n + 1)
maxnode = [i for i in range(n + 1)]
max_ = 0
for j in range(m):
	(b, c) = map(int, input().split())
	max_ = max(max_, max(b, c))
	ro1 = root(b)
	ro2 = root(c)
	if c > maxnode[ro1]:
		maxnode[ro1] = c
	if b > maxnode[ro2]:
		maxnode[ro2] = b
	if ro1 != ro2:
		if sz[ro1] >= sz[ro2]:
			sz[ro1] += sz[ro2]
			sz[ro2] = 0
			l[ro2] = ro1
		else:
			sz[ro2] += sz[ro1]
			sz[ro1] = 0
			l[ro1] = ro2
end = 0
j = 0
while end < max_:
	for k in range(end, n):
		if maxnode[k] > k:
			kj = maxnode[k]
			jk = max(maxnode[k:maxnode[k]])
			while jk > kj:
				h = jk
				jk = max(maxnode[kj:jk])
				kj = h
			end = kj
			break
	for i in range(kj, k - 1, -1):
		if l[root(i)] != root(k):
			l[root(i)] = root(k)
			j += 1
print(j)


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
used = set()
ans = 0
mp = -1
for i in range(N):
	if i in used:
		continue
	if mp >= i:
		ans += 1
		Edge[mp].append(i)
		Edge[i].append(mp)
		mp = max(mp, i)
	else:
		st = i
	stack = [i]
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf not in used:
				mp = max(mp, vf)
				used.add(vf)
				stack.append(vf)
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(N, M) = list(map(int, input().split()))
P = [-1 for i in range(N)]

def par(a):
	L = []
	while P[a] >= 0:
		L.append(a)
		a = P[a]
	for l in L:
		P[l] = a
	return a

def unite(a, b):
	if par(a) == par(b):
		return 0
	if P[par(b)] == P[par(a)]:
		P[par(b)] = par(a)
		P[par(a)] -= 1
	elif P[par(b)] > P[par(a)]:
		P[par(b)] = par(a)
	else:
		P[par(a)] = par(b)
for _ in range(M):
	(u, v) = list(map(int, input().split()))
	unite(u - 1, v - 1)
C = [[] for _ in range(N)]
D = [0] * N
for i in range(N):
	C[par(i)].append(i)
	D[par(i)] = 1
ma = -1
ans = 0
for i in range(N):
	p = par(i)
	if D[p] == 0:
		continue
	D[p] = 0
	if min(C[p]) < ma:
		ans += 1
	ma = max(ma, max(C[p]))
print(ans)


class DS(list):

	def __init__(self, n):
		self.pa = [i for i in range(n)]
		self.r = [i for i in range(n)]
		self.n = n

	def get(self, i):
		j = self.pa[i]
		if j != i and self.pa[j] != j:
			pa = self.pa
			while pa[j] != j:
				j = pa[j]
			while pa[i] != j:
				k = pa[i]
				pa[i] = j
				i = k
		return j

	def join(self, i, j):
		i = self.get(i)
		j = self.get(j)
		self.pa[i] = j
		self.r[j] = max(self.r[j], self.r[i])
import sys
stdin = iter(sys.stdin.read().split())
n = int(next(stdin))
m = int(next(stdin))
ds = DS(n)
for _ in range(m):
	i = int(next(stdin))
	j = int(next(stdin))
	ds.join(i - 1, j - 1)
ans = 0
for i in range(n):
	if i + 1 <= ds.r[ds.get(i)] and ds.get(i) != ds.get(i + 1):
		ds.join(i, i + 1)
		ans += 1
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edge = [[] for _ in [0] * n]
for i in range(m):
	(u, v) = map(int, input().split())
	edge[u - 1].append(v - 1)
	edge[v - 1].append(u - 1)
ma = [-1] * n
for i in range(n):
	if ma[i] != -1:
		continue
	tank = []
	new = [i]
	tmp = i
	while len(new) > 0:
		tank = []
		for e in new:
			for go in edge[e]:
				if ma[go] == -1:
					ma[go] = -2
					tmp = max(tmp, go)
					tank.append(go)
		new = tank
	ma[i] = tmp
res = 0
p = -1
for i in range(n):
	if ma[i] >= 0:
		if i < p:
			res += 1
		p = max(p, ma[i])
print(res)


class Uf:

	def __init__(self, N):
		self.p = list(range(N))
		self.rank = [0] * N
		self.size = [1] * N

	def root(self, x):
		if self.p[x] != x:
			self.p[x] = self.root(self.p[x])
		return self.p[x]

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

	def unite(self, x, y):
		u = self.root(x)
		v = self.root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
			self.size[v] += self.size[u]
			self.size[u] = 0
		else:
			self.p[v] = u
			self.size[u] += self.size[v]
			self.size[v] = 0
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1

	def count(self, x):
		return self.size[self.root(x)]
import sys
from operator import itemgetter

def main():
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	uf = Uf(N + 1)
	for (u, v) in zip(*[iter(map(int, sys.stdin.read().split()))] * 2):
		uf.unite(u, v)
	L = [10 ** 9] * (N + 1)
	R = [-1] * (N + 1)
	for i in range(1, N + 1):
		r = uf.root(i)
		L[r] = min(L[r], i)
		R[r] = max(R[r], i)
	ans = 0
	LR = []
	for (l, r) in zip(L, R):
		if r != -1:
			LR.append((l, r))
	LR.sort(key=itemgetter(0))
	rr = -1
	for (l, r) in LR:
		if rr > l:
			ans += 1
		rr = max(rr, r)
	print(ans)
main()


import sys
input = sys.stdin.readline
from collections import defaultdict as dd, deque as dq

def bfs(vis, u, d):
	l = []
	q = dq([u])
	while q:
		u = q.popleft()
		vis[u] = 1
		l.append(u)
		for j in d[u]:
			if vis[j] == -1:
				q.append(j)
	return (min(l), max(l))
(n, m) = map(int, input().split())
d = dd(list)
while m:
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
	m -= 1
vis = [-1] * (n + 1)
seg = []
for i in range(1, n + 1):
	if vis[i] == -1:
		seg.append(bfs(vis, i, d))
seg.sort()
mi = seg[0][0]
mx = seg[0][1]
cou = 0
for i in range(1, len(seg)):
	if seg[i][0] >= mi and seg[i][0] <= mx:
		cou += 1
		mx = max(seg[i][1], mx)
	else:
		mx = max(seg[i][1], mx)
print(cou)


import sys
input = sys.stdin.readline
from collections import deque
inf = int(10000000000.0)
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
v = [0] * n
ans = []
for i in range(n):
	if not v[i]:
		q = deque([i])
		v[i] = 1
		(mn, mx) = (inf, -1)
		while q:
			node = q.popleft()
			(mn, mx) = (min(mn, node), max(mx, node))
			for j in graph[node]:
				if not v[j]:
					v[j] = 1
					q.append(j)
		ans.append((mn, 0))
		ans.append((mx, 1))
ans.sort()
count = 0
final = 0
for i in ans:
	if i[1] == 0:
		count += 1
		if count > 1:
			final += 1
	if i[1] == 1:
		count -= 1
print(final)


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
(n, m) = mdata()
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		if Nodes[find(x)] < Nodes[find(y)]:
			Nodes[find(y)] += Nodes[find(x)]
			Nodes[find(x)] = 0
			Group[find(x)] = find(y)
		else:
			Nodes[find(x)] += Nodes[find(y)]
			Nodes[find(y)] = 0
			Group[find(y)] = find(x)
for i in range(m):
	(x, y) = mdata()
	Union(x, y)
d = dd(int)
for i in range(1, n + 1):
	d[find(i)] = i
ans = 0
m = 1
for i in range(1, n + 1):
	if m > d[find(i)]:
		d[find(i)] = m
		Union(m, i)
		ans += 1
	else:
		m = d[find(i)]
print(ans)


import sys
ints = (int(x) for x in sys.stdin.read().split())

class DS(list):

	def __init__(self, n):
		self[:] = [i for i in range(n)]

	def get(self, i):
		j = self[i]
		if self[j] != j:
			while self[j] != j:
				j = self[j]
			while self[i] != j:
				k = self[i]
				self[i] = j
				i = k
		return j

	def join(self, i, j):
		i = self.get(i)
		j = self.get(j)
		self[i] = j

class DS2(DS):

	def __init__(self, n):
		super().__init__(n)
		self.r = [i for i in range(n)]

	def join(self, i, j):
		i = self.get(i)
		j = self.get(j)
		self[i] = j
		self.r[j] = max(self.r[j], self.r[i])
n = next(ints)
m = next(ints)
ds = DS2(n)
E = [(next(ints) - 1, next(ints) - 1) for _ in range(m)]
for (i, j) in E:
	ds.join(i, j)
ans = 0
for i in range(n):
	if i + 1 <= ds.r[ds.get(i)] and ds.get(i) != ds.get(i + 1):
		ds.join(i, i + 1)
		ans += 1
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bs(a, l, h, x):
	while l < h:
		mid = (l + h) // 2
		if a[mid] == x:
			return mid
		if a[mid] < x:
			l = mid + 1
		else:
			h = mid
	return l

def bfs(g, st):
	visited = [-1] * len(g)
	visited[st] = 0
	queue = []
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.pop()
		new.append(s)
		for i in g[s]:
			if visited[i] == -1:
				visited[i] = visited[s] + 1
				queue.append(i)
	return visited

def dfsusingstack(v, st, visited, currmin, currmax):
	d = deque([])
	d.append(st)
	new = []
	visited[st] = 1
	while len(d) != 0:
		curr = d.pop()
		currmin = min(currmin, curr)
		currmax = max(currmax, curr)
		new.append(curr)
		for i in v[curr]:
			if visited[i] == 0:
				visited[i] = 1
				d.append(i)
	return [currmin, currmax]

def sieve(a, n):
	for i in range(3, n + 1, 2):
		a[i] = 1
	for i in range(3, n + 1, 2):
		for j in range(i * i, n + 1, i):
			a[j] = 0
	a[2] = 1
	return a

def solve():
	(n, m) = sep()
	graph = [[] for i in range(n + 1)]
	mm = 0
	for i in range(m):
		(a, b) = sep()
		graph[a].append(b)
		graph[b].append(a)
		mm = max(mm, max(a, b))
	ans = 0
	visited = [0] * (n + 1)
	storage = []
	for ii in range(1, n + 1):
		curr = ii
		if visited[curr] == 0:
			currmin = curr
			currmax = curr
			new = dfsusingstack(graph, curr, visited, currmin, currmax)
			storage.append(new)
	currmax = -1
	for i in range(0, len(storage)):
		if storage[i][0] < currmax:
			ans += 1
		currmax = max(currmax, storage[i][1])
	print(ans)
testcase(1)


class DS(list):

	def __init__(self, n):
		self.pa = [i for i in range(n)]
		self.r = [i for i in range(n)]
		self.n = n

	def get(self, i):
		j = self.pa[i]
		if j != i and self.pa[j] != j:
			pa = self.pa
			while pa[j] != j:
				j = pa[j]
			while pa[i] != j:
				k = pa[i]
				pa[i] = j
				i = k
		return j

	def join(self, i, j):
		i = self.get(i)
		j = self.get(j)
		self.pa[i] = j
		self.r[j] = max(self.r[j], self.r[i])
from collections import deque
import sys
ints = deque((int(x) for x in sys.stdin.read().split()))
n = ints.popleft()
m = ints.popleft()
ds = DS(n)
for _ in range(m):
	i = ints.popleft()
	j = ints.popleft()
	ds.join(i - 1, j - 1)
ans = 0
for i in range(n):
	if i + 1 <= ds.r[ds.get(i)] and ds.get(i) != ds.get(i + 1):
		ds.join(i, i + 1)
		ans += 1
print(ans)


class union_find:

	def __init__(self, n):
		self.n = n
		self.rank = [0] * n
		self.parent = [[int(j), int(j), int(j)] for j in range(n)]

	def union(self, i, j):
		i = self.find(i)
		j = self.find(j)
		if self.rank[i] <= self.rank[j]:
			self.parent[i][0] = j
			self.parent[j][1] = min(self.parent[i][1], self.parent[j][1])
			self.parent[j][2] = max(self.parent[i][2], self.parent[j][2])
			self.rank[j] += 1
		elif self.rank[i] > self.rank[j]:
			self.parent[j][0] = i
			self.parent[i][1] = min(self.parent[i][1], self.parent[j][1])
			self.parent[i][2] = max(self.parent[i][2], self.parent[j][2])

	def find(self, i):
		temp = i
		if self.parent[temp][0] != temp:
			self.parent[temp][0] = self.find(self.parent[temp][0])
		return self.parent[temp][0]
import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m) = [int(j) for j in input().split()]
	x = union_find(n + 1)
	for i in range(m):
		(y, z) = [int(j) for j in input().split()]
		x.union(y, z)
	s = set()
	for i in range(1, n + 1):
		b = x.find(i)
		s.add(b)
	ans = 0
	rt = 0
	for i in s:
		if rt < x.parent[i][2]:
			rt = x.parent[i][2]
			for j in range(x.parent[i][1], x.parent[i][2] + 1):
				if x.find(j) != x.find(i):
					x.union(i, j)
					ans += 1
	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) = map(int, input().split())
G = [[] for i in range(n + 1)]
visited = [False for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
s = 0
m = i = 1
stack = [i]
while i <= n:
	while len(stack) > 0:
		v = stack.pop()
		visited[v] = True
		m = max(m, v)
		for e in G[v]:
			if not visited[e]:
				stack.append(e)
				visited[e] = True
	while i <= n and visited[i]:
		i += 1
	if i <= m:
		s += 1
	stack.append(i)
print(s)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left

def dfs(x):
	stack = [x]
	t = 0
	while stack:
		x = stack.pop()
		t = max(t, x)
		visited[x] = 1
		for i in graph[x]:
			if visited[i] == 0:
				stack.append(i)
	return t
(n, m) = map(int, input().split())
graph = {}
visited = [0 for i in range(200003)]
count = 0
ma = 0
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in graph:
		graph[a] = set()
	if b not in graph:
		graph[b] = set()
	graph[a].add(b)
	graph[b].add(a)
for i in range(1, 200001):
	if visited[i] == 0:
		if i in graph:
			if i <= ma:
				count += 1
			ma = max(ma, dfs(i))
		elif i <= ma:
			count += 1
			visited[i] = 1
print(count)


import sys
from sys import stdin, stdout
sys.setrecursionlimit(200001)
visit = []

def bfs(adj, i, m):
	queue = []
	queue.append(i)
	visit[i] = 1
	while queue:
		h = queue.pop()
		if h > m:
			m = h
		visit[h] = 1
		for j in adj[h]:
			if visit[j] == 0:
				visit[j] = 1
				queue.append(j)
	return m
(n, m) = stdin.readline().split()
n = int(n)
m = int(m)
adj = [[] for _ in range(n + 1)]
while m > 0:
	(x, y) = stdin.readline().split()
	x = int(x)
	y = int(y)
	adj[x].append(y)
	adj[y].append(x)
	m -= 1
visit = [0] * (n + 1)
result = 0
count = 0
k = 0
for i in range(1, n + 1):
	if visit[i] == 0:
		if count > 0 and i < k:
			result += 1
		if visit[i] == 0 and len(adj[i]) > 0:
			count += 1
			k = bfs(adj, i, k)
stdout.write(str(result))


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def Find_Root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.Find_Root(self.root[x])
			return self.root[x]

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return -self.root[self.Find_Root(x)]
import sys
input = sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	uni = UnionFind(N)
	for _ in range(M):
		(a, b) = map(int, input().split())
		uni.Unite(a, b)
	R = {}
	for n in range(1, N + 1):
		R[uni.Find_Root(n)] = n
	ans = 0
	root = uni.Find_Root(1)
	max_n = R[root]
	for n in range(1, N + 1):
		rn = uni.Find_Root(n)
		if n > max_n:
			root = rn
			max_n = R[root]
		elif root != rn:
			ans += 1
			uni.Unite(root, rn)
			root = uni.Find_Root(root)
			max_n = max(max_n, R[rn])
	print(ans)
main()


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

class DisjointSet:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.size = [1] * n
		self.rank = [0] * n
		self.max_member = [i for i in range(n)]

	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def has_same_root(self, x, y):
		return self.root(x) == self.root(y)

	def get_size(self, x):
		return self.size[self.root(x)]

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.max_member[y] = max(self.max_member[x], self.max_member[y])
		else:
			self.par[y] = x
			self.max_member[x] = max(self.max_member[x], self.max_member[y])
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
(n, m) = [int(item) for item in input().split()]
DS = DisjointSet(n)
for i in range(m):
	(u, v) = [int(item) - 1 for item in input().split()]
	DS.unite(u, v)
goal = 0
par = 0
ans = 0
for i in range(n):
	if goal <= i:
		par = DS.par[i]
		goal = DS.max_member[par]
		continue
	if DS.has_same_root(par, i):
		continue
	else:
		DS.unite(par, i)
		ans += 1
		par = DS.par[i]
		goal = DS.max_member[par]
print(ans)


from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10 ** 8)

def inpl(k=0):
	return [int(x) + k for x in sys.stdin.readline().split()]
visited = [False] * 200100
lines = defaultdict(set)

def dfs(s):
	global visited
	visited[s] = True
	ret = s
	for t in lines[s]:
		if visited[t] == False:
			ret = max(dfs(t), ret)
	return ret

def main():
	global visited
	(N, M) = inpl()
	for _ in range(M):
		(x, y) = inpl(-1)
		lines[x].add(y)
		lines[y].add(x)
	maxr = 0
	ans = 0
	for l in range(N):
		if visited[l] == False:
			r = dfs(l)
			if l < maxr:
				ans += 1
			maxr = max(r, maxr)
	print(ans)
threading.stack_size(1024 * 100000)
thread = threading.Thread(target=main)
thread.start()
thread.join()


from collections import defaultdict
import threading, sys
sys.setrecursionlimit(10 ** 8)
visited = [False] * 200010
graph = defaultdict(set)

def read():
	return sys.stdin.readline().split()

def dfs(start):
	visited[start] = True
	ret = start
	for v in graph[start]:
		if not visited[v]:
			ret = max(dfs(v), ret)
	return ret

def main():
	(n, m) = map(int, read())
	for _ in range(m):
		(u, v) = map(int, read())
		(u, v) = (u - 1, v - 1)
		graph[u].add(v)
		graph[v].add(u)
	max_r = 0
	ans = 0
	for l in range(n):
		if not visited[l]:
			r = dfs(l)
			if l < max_r:
				ans += 1
			max_r = max(r, max_r)
	print(ans)
threading.stack_size(1024 * 100000)
thread = threading.Thread(target=main)
thread.start()
thread.join()


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.right = [i for i in range(n)]

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def union(self, x, y):
		root_x = self.root(x)
		root_y = self.root(y)
		if root_x == root_y:
			return False
		if self.parent[root_x] > self.parent[root_y]:
			(root_x, root_y) = (root_y, root_x)
		self.parent[root_x] += self.parent[root_y]
		self.parent[root_y] = root_x
		self.right[root_x] = max(self.right[root_x], self.right[root_y])
		return True
(n, m) = map(int, input().split())
UF = UnionFind(n)
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	UF.union(a, b)
ans = 0
i = 0
while i < n:
	par = UF.root(i)
	right = UF.right[par]
	if i == right:
		i += 1
		continue
	for j in range(i + 1, right + 1):
		ans += UF.union(i, j)
	i = right
print(ans)


from collections import deque
from sys import stdin
(n, m) = map(int, input().split())
ans = 0
ma = 0
(check, have) = ([0] * (n + 1), [0] * (n + 1))
node = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, stdin.readline().split())
	node[a].append(b)
	node[b].append(a)
	have[a] = have[b] = 1

def bfs(s):
	global node, check, ma
	q = deque()
	q.append(s)
	while len(q) > 0:
		p = q[0]
		q.popleft()
		for i in node[p]:
			if check[i] == 0:
				check[i] = 1
				q.append(i)
				ma = max(ma, i)
for i in range(1, n + 1):
	if check[i] == 0 and i <= ma:
		bfs(i)
		ans += 1
	elif check[i] == 0 and have[i] == 1:
		bfs(i)
print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = [int(s) for s in input().split()]
parent = [i for i in range(n + 1)]

def find(a):
	a1 = a
	while a != parent[a]:
		a = parent[a]
	parent[a1] = a
	return a
for i in range(m):
	(u, v) = [int(s) for s in input().split()]
	pv = find(v)
	pu = find(u)
	if pu < pv:
		(pu, pv) = (pv, pu)
	parent[pv] = pu
for i in range(n, 0, -1):
	parent[i] = find(i)
ans = 0
bar = 0
for i in range(n):
	bar = max(bar, parent[i])
	if parent[i] == i:
		if bar == i:
			bar = i + 1
		else:
			ans += 1
print(ans)


import sys, os, io
from sys import stdin
import math
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
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')
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)
	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:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
mex = 0
vis = [False] * 200001

@bootstrap
def dfs(node):
	global mex
	for kid in adj[node]:
		if vis[kid] == False:
			vis[kid] = True
			mex = max(mex, kid)
			yield dfs(kid)
	yield
(n, m) = li()
adj = [[] for i in range(n)]
for i in range(m):
	(u, v) = li()
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
ans = 0
for i in range(n):
	if vis[i] == False:
		vis[i] = True
		if i < mex:
			ans += 1
		dfs(i)
print(ans)


import sys
input = sys.stdin.readline
(n, m) = [int(s) for s in input().split()]
parent = [i for i in range(n + 1)]

def find(a):
	while a != parent[a]:
		a2 = a
		a = parent[a]
		parent[a2] = parent[a]
	return a
for i in range(m):
	(u, v) = [int(s) for s in input().split()]
	pv = find(v)
	pu = find(u)
	if pu > pv:
		(pu, pv) = (pv, pu)
	parent[pv] = pu
ans = 0
bar = n
for i in range(n, 0, -1):
	parent[i] = find(i)
	bar = min(bar, parent[i])
	if parent[i] == i:
		if bar == i:
			bar = i - 1
		else:
			ans += 1
print(ans)


from collections import defaultdict
import sys, threading
sys.setrecursionlimit(10 ** 8)

def main():
	(n, m) = map(int, input().split())
	g = {}
	for i in range(1, n + 1):
		g[i] = []
	for i in range(m):
		(a, b) = map(int, input().split())
		g[a].append(b)
		g[b].append(a)
	used = [False for i in range(n + 1)]
	comp = []

	def dfs(v):
		used[v] = True
		if len(comp) >= 2:
			if v < comp[0]:
				comp[0] = v
			if v > comp[-1]:
				comp[-1] = v
		else:
			comp.append(v)
		for i in range(len(g[v])):
			to = g[v][i]
			if not used[to]:
				dfs(to)

	def find():
		for i in range(1, n + 1):
			if not used[i]:
				comp.clear()
				dfs(i)
				e = comp
				res.append((e[0], e[-1]))
	res = []
	find()
	ans = 0
	cur = res[0][1]
	for (cmn, cmx) in res[1:]:
		if cmn <= cur:
			ans += 1
		cur = max(cmx, cur)
	print(ans)
threading.stack_size(1024 * 100000)
thread = threading.Thread(target=main)
thread.start()
thread.join()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
(n, m) = map(int, input().split())
adj = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
cmps = []
v = [0] * (n + 1)
for i in range(1, n + 1):
	if not v[i]:
		q = [i]
		mn = 1e+18
		mx = 0
		while q:
			e = q.pop()
			mn = min(e, mn)
			mx = max(e, mx)
			v[e] = 1
			for j in adj[e]:
				if not v[j]:
					q.append(j)
		cmps.append((mn, mx))
ct = 0
cmps.sort(key=lambda x: x[0])
bg = cmps[0][1]
for i in cmps[1:]:
	if i[0] < bg:
		ct += 1
	bg = max(bg, i[1])
print(ct)


import os
import sys
from io import BytesIO, IOBase
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 math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, m) = RL()
	arr = [i for i in range(n + 1)]

	def union(a, b):
		(pa, pb) = (find(a), find(b))
		if pa != pb:
			if pa > pb:
				arr[pa] = pb
			else:
				arr[pb] = pa

	def find(a):
		ta = a
		while a != arr[a]:
			a = arr[a]
		arr[ta] = a
		return a
	for _ in range(m):
		(f, t) = RL()
		union(f, t)
	recm = [i for i in range(n + 1)]
	for i in range(1, n + 1):
		recm[i] = find(i)
	res = 0
	mi = n
	for i in range(n, 0, -1):
		nd = find(i)
		if mi < recm[nd]:
			recm[nd] = min(recm[find(mi)], recm[nd])
			union(mi, nd)
			res += 1
		else:
			mi = recm[nd]
	print(res)
main()


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes
from collections import Counter

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		graph = [[] for i in range(n + 1)]
		visited = [0] * (n + 1)
		for i in range(m):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)

		def dfs(start):
			mx = start
			stack = [start]
			while stack:
				start = stack[-1]
				if not visited[start]:
					mx = max(mx, start)
					visited[start] = True
					for child in graph[start]:
						if not visited[child]:
							stack.append(child)
				else:
					stack.pop()
			return mx
		ans = 0
		currlow = 1
		currmax = 1
		for i in range(1, n + 1):
			if i > currmax:
				currmax = i
				currlow = i
			if not visited[i]:
				if currlow < i < currmax:
					ans += 1
				currmax = max(currmax, dfs(i))
		wi(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			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, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			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()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

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

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


def main():
	from sys import stdin, stdout
	from array import array
	(n, m) = map(int, stdin.readline().split())
	n += 1
	g = [array('l', ()) for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, stdin.readline().split())
		g[u].append(v)
		g[v].append(u)
	ans = 0
	new = array('i', (1,)) * n
	vr = 0
	for v1 in range(n):
		if new[v1]:
			if v1 < vr:
				ans += 1
			stack = [v1]
			while stack:
				u = stack.pop()
				if new[u]:
					new[u] = 0
					vr = max(vr, u)
					for v in g[u]:
						stack.append(v)
	print(ans)
main()


import sys
import collections
import heapq
import math
input = sys.stdin.readline

def rints():
	return map(int, input().strip().split())

def rstr():
	return input().strip()

def rint():
	return int(input().strip())

def rintas():
	return [int(i) for i in input().strip().split()]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
(n, m) = rints()
graphs = collections.defaultdict(list)
nums = set()
for _ in range(m):
	(u, v) = rints()
	graphs[u].append(v)
	graphs[v].append(u)
	nums.add(u)
	nums.add(v)
times = list()
seen = set()
for i in nums:
	if i in seen:
		continue
	(mn, mx) = (i, i)
	queue = []
	queue.append(i)
	while queue:
		cur = queue.pop()
		if cur in seen:
			continue
		seen.add(cur)
		mn = min(mn, cur)
		mx = max(mx, cur)
		for k in graphs[cur]:
			queue.append(k)
	times.append([mn, mx])
times.sort()
(u, v) = times[0]
ans = 0
merges = list()
for i in range(1, len(times)):
	(i, j) = times[i]
	if i <= v:
		ans += 1
		v = max(v, j)
	else:
		merges.append([u, v])
		(u, v) = (i, j)
merges.append([u, v])
for (u, v) in merges:
	for x in range(u, v + 1):
		if x not in seen:
			ans += 1
print(ans)


from collections import deque
(n, m) = map(int, input().split())
a = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	a[x].append(y)
	a[y].append(x)
vis = [1] * (n + 1)
c = 0
m = 1
for i in range(1, n + 1):
	if vis[i]:
		if i < m:
			c += 1
		s = deque([i])
		while s:
			x = s.popleft()
			if vis[x]:
				s += a[x]
				vis[x] = 0
				if x > m:
					m = x
print(c)


import sys
from collections import defaultdict as dd
pl = 1
from math import *
import copy
if pl:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())
d = []
from bisect import *
from itertools import permutations
from collections import deque

def siv(n):
	prime = [True for i in range(n + 1)]
	p = 2
	if 1:
		while p * p <= n:
			if prime[p] == True:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1
		for p in range(2, n + 1):
			if prime[p]:
				d.append(p)
(n, m) = mi()

def find(i, a):
	if a[i] == i:
		return i
	a[i] = find(a[i], a)
	return a[i]

def union(x, y, a):
	xs = find(x, a)
	ys = find(y, a)
	if xs == ys:
		return False
	if rank[xs] < rank[ys]:
		(xs, ys) = (ys, xs)
	rank[xs] += 1
	a[ys] = xs
	return True
a = [i for i in range(n + 1)]
rank = [0 for i in range(n + 1)]
p = [[-1, -1] for i in range(n + 1)]
for i in range(m):
	(x, y) = mi()
	union(x, y, a)
for i in range(1, n + 1):
	a[i] = find(i, a)
	if p[a[i]][0] == -1:
		p[a[i]] = [i, i]
	else:
		p[a[i]][1] = i
i = 0
c = 0
while i <= n:
	l = i
	i += 1
	if i > n:
		break
	j = p[a[l]][1]
	while i <= j:
		if a[l] != a[i]:
			j = max(j, p[a[i]][1])
			if union(i, l, a):
				c += 1
		i += 1
print(c)


import sys
(n, m) = map(int, sys.stdin.readline().split())
G = [[] for i in range(n + 1)]
visited = [False for i in range(n + 1)]
for i in range(m):
	(u, v) = [int(x) for x in sys.stdin.readline().split()]
	G[v].append(u)
	G[u].append(v)
s = 0
i = m = 1
stack = [i]
while i <= n:
	while len(stack) > 0:
		v = stack.pop()
		visited[v] = True
		if v > m:
			m = v
		for e in G[v]:
			if not visited[e]:
				stack.append(e)
				visited[e] = True
	while i <= n and visited[i]:
		i += 1
	if i <= m:
		s += 1
	stack.append(i)
print(s)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()

def addEdge(a, b):
	graph[a].append(b)
	graph[b].append(a)

def Bfs(src):
	q = deque([])
	q.append(src)
	visited[src] = True
	ma = src
	mi = src
	while q:
		node = q.popleft()
		ma = max(node, ma)
		mi = min(node, mi)
		for neighbour in graph[node]:
			if not visited[neighbour]:
				q.append(neighbour)
				visited[neighbour] = True
	return (mi, ma)
t = 1
for _ in range(t):
	(n, m) = inp()
	visited = [False] * n
	graph = [[] for i in range(n)]
	for i in range(m):
		(a, b) = inp()
		addEdge(a - 1, b - 1)
	check = []
	ans = 0
	for i in range(n):
		if not visited[i]:
			(mi, ma) = Bfs(i)
			temp = [mi, ma]
			check.append(temp)
	cur = -1
	for i in range(len(check)):
		if check[i][0] <= cur:
			ans += 1
		cur = max(check[i][1], cur)
	print(ans)


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)

def main():

	def getFurthestForward(node):
		if len(adj[node]) == 0:
			return -1
		temp = max(adj[node])
		if temp <= node:
			return -1
		return temp
	(n, m) = readIntArr()
	adj = [[] for _ in range(n)]
	uf = UnionFind(n)
	for __ in range(m):
		(u, v) = readIntArr()
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
		uf.union(u, v)
	ans = 0
	i = 0
	while i < n:
		j = getFurthestForward(i)
		if j == -1:
			i += 1
			continue
		zz = i + 1
		while zz <= j:
			if uf.find(i) != uf.find(zz):
				ans += 1
				uf.union(i, zz)
			j = max(j, getFurthestForward(zz))
			zz += 1
		i = j + 1
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([''.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
vis = [0] * n
m = -1
ans = 0
for i in range(n):
	if not vis[i]:
		if i < m:
			ans += 1
		queue = [i]
		queue = deque(queue)
		while len(queue) != 0:
			e = queue.popleft()
			m = max(e, m)
			vis[e] = 1
			for i in graph[e]:
				if not vis[i]:
					queue.append(i)
					vis[i] = 1
print(ans)


from sys import stdin
input = stdin.readline
edge = [[] for _ in range(200005)]
(n, m) = map(int, input().split())
check = [0] * 200005
mx = 0
from collections import deque

def dfs(x):
	l = deque([x])
	check[x] = 1
	while len(l):
		p = l.popleft()
		global mx
		mx = max(mx, p)
		for i in edge[p]:
			if check[i]:
				continue
			l.append(i)
			check[i] = 1
for i in range(m):
	(u, v) = map(int, input().split())
	edge[u].append(v)
	edge[v].append(u)
r = 0
ans = 0
for i in range(1, n + 1):
	if check[i]:
		continue
	mx = 0
	dfs(i)
	if i <= r:
		ans += 1
	r = max(r, mx)
print(ans)


import sys

class DHarmoniousGraph:

	def solve(self):
		from collections import defaultdict

		class Node:

			def __init__(self, val):
				self.parent = self
				self.size = 1
				self.val = val

		def union(x, y):
			(xRoot, yRoot) = (find(x), find(y))
			if xRoot == yRoot:
				return
			if xRoot.size >= yRoot.size:
				yRoot.parent = xRoot
				xRoot.size += yRoot.size
			else:
				xRoot.parent = yRoot
				yRoot.size += xRoot.size

		def find(x):
			while x.parent != x:
				x = x.parent
			return x
		(n, m) = [int(_) for _ in input().split()]
		adj = defaultdict(list)
		nodes = [Node(i) for i in range(n)]
		parent = [-1] * n
		for i in range(m):
			(u, v) = [int(_) for _ in input().split()]
			u -= 1
			v -= 1
			adj[u].append(v)
			adj[v].append(u)
			union(nodes[u], nodes[v])
		for i in range(n):
			parent[i] = find(nodes[i]).val
		cc = defaultdict(tuple)
		for g in parent:
			cc[g] = (float('inf'), -float('inf'))
		for i in range(n):
			g = parent[i]
			cc[g] = (min(cc[g][0], i), max(cc[g][1], i))
		ccs = [[g, cc[g][0], cc[g][1]] for g in cc]
		ccs.sort(key=lambda x: x[1])
		ans = 0
		done = {g: 0 for g in cc}
		for (g, cur, r) in ccs:
			if done[g]:
				continue
			while cur < r:
				cur_p = find(nodes[cur])
				r_p = find(nodes[r])
				if cur_p != r_p:
					ans += 1
					done[cur_p.val] = 1
					new_r = max(r, cc[cur_p.val][1])
					union(nodes[cur], nodes[r])
					r = new_r
				cur += 1
		print(ans)
solver = DHarmoniousGraph()
input = sys.stdin.readline
solver.solve()


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(300000)
(n, m) = map(int, input().split())
(sn, smx) = (list(range(n + 1)), list(range(n + 1)))

def s_find(u):
	p = []
	while sn[u] != u:
		p.append(u)
		u = sn[u]
	for v in p:
		sn[v] = u
	return u

def s_union(u, v):
	(su, sv) = (s_find(u), s_find(v))
	if su == sv:
		return False
	smx[su] = max(smx[su], smx[sv])
	sn[sv] = su
	return True
for i in range(m):
	(a, b) = map(int, input().split())
	s_union(a, b)
cc = 0
for u in range(1, n + 1):
	su = s_find(u)
	if u < smx[su] and s_union(u, u + 1):
		cc += 1
print(cc)


import sys
from collections import defaultdict
(n, m) = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
dic = defaultdict(int)
rem = defaultdict(list)
for i in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	graph[u].append(v)
	graph[v].append(u)
vis = defaultdict(int)
arr = []
for i in range(1, n + 1):
	if vis[i] == 0:
		l = []
		q = [i]
		while q:
			a = q.pop()
			l.append(a)
			vis[a] = 1
			for j in graph[a]:
				if vis[j] == 0:
					q.append(j)
					vis[j] = 1
		arr.append(l)
n = len(arr)
l = [0 for _ in range(n)]
for i in range(n):
	l[i] = [min(arr[i]), max(arr[i])]
l.sort()
(low, high) = (l[0][0], l[0][1])
ans = 0
for i in range(1, n):
	if l[i][0] > high:
		low = l[i][0]
		high = l[i][1]
	else:
		if l[i][0] < low:
			low = l[i][0]
		if l[i][1] > high:
			high = l[i][1]
		ans += 1
print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def root(k):
	while k != l[k]:
		k = l[l[k]]
	return k
(n, m) = map(int, input().split())
l = [i for i in range(n + 1)]
sz = [1] * (n + 1)
maxnode = [i for i in range(n + 1)]
max_ = 0
for j in range(m):
	(b, c) = map(int, input().split())
	max_ = max(max_, max(b, c))
	ro1 = root(b)
	ro2 = root(c)
	if c > maxnode[ro1]:
		maxnode[ro1] = c
	if b > maxnode[ro2]:
		maxnode[ro2] = b
	if ro1 != ro2:
		if sz[ro1] >= sz[ro2]:
			sz[ro1] += sz[ro2]
			sz[ro2] = 0
			l[ro2] = ro1
		else:
			sz[ro2] += sz[ro1]
			sz[ro1] = 0
			l[ro1] = ro2
end = 0
j = 0
while end < max_:
	for k in range(end, n):
		if maxnode[k] > k:
			kj = maxnode[k]
			jk = max(maxnode[k:maxnode[k]])
			while jk > kj:
				h = jk
				jk = max(maxnode[kj:jk])
				kj = h
			end = kj
			break
	for i in range(kj, k - 1, -1):
		if l[root(i)] != root(k):
			l[root(i)] = root(k)
			j += 1
print(j)


from collections import defaultdict, deque
import sys
import os

def get_neighbors(edges):
	neighbors = defaultdict(set, {})
	for (v1, v2) in edges:
		if v1 != v2:
			neighbors[v1].add(v2)
			neighbors[v2].add(v1)
	return dict(neighbors)

def connected_components(edges, n):
	adj = get_neighbors(edges)
	seen = set()
	node_to_comp = [-1] * (n + 1)
	component_to_max_node = [-1] * (n + 1)
	component = 0
	for root in adj:
		if root in seen:
			continue
		fringe = deque([root])
		while fringe:
			node = fringe.pop()
			seen.add(node)
			node_to_comp[node] = component
			component_to_max_node[component] = max(component_to_max_node[component], node)
			for new_node in adj[node]:
				if new_node not in seen:
					seen.add(new_node)
					fringe.appendleft(new_node)
		component += 1
	return (component_to_max_node[:component], node_to_comp)

def connected_components3(edges):
	adj = get_neighbors(edges)
	seen = set()
	components = []
	for root in adj:
		if root in seen:
			continue
		component = []
		fringe = deque([root])
		while fringe:
			node = fringe.pop()
			seen.add(node)
			component.append(node)
			for new_node in adj[node]:
				if new_node not in seen:
					seen.add(new_node)
					fringe.appendleft(new_node)
		components.append(component)
	return components

def solve(edges, n):
	(component_to_max_node, node_to_comp) = connected_components(edges, n)
	seen_comps = set()
	min_node = 1
	cost = 0
	while min_node <= n:
		component = node_to_comp[min_node]
		if component == -1:
			min_node += 1
			continue
		seen_comps.add(node_to_comp[min_node])
		max_node = component_to_max_node[node_to_comp[min_node]]
		j = min_node + 1
		while j <= max_node:
			if node_to_comp[j] == -1 or node_to_comp[j] not in seen_comps:
				seen_comps.add(node_to_comp[j])
				cost += 1
			if node_to_comp[j] >= 0 and component_to_max_node[node_to_comp[j]] > max_node:
				max_node = component_to_max_node[node_to_comp[j]]
			j += 1
		min_node = max_node + 1
	return cost

def pp(input):
	(n, m) = map(int, input().split())
	edges = [tuple(map(int, input().split())) for _ in range(m)]
	print(solve(edges, n))
if 'paalto' in os.getcwd():
	from string_source import string_source
	pp(string_source('500 5\n100 300\n200 400\n420 440\n430 450\n435 460'))
	pp(string_source('14 8\n    1 2\n    2 7\n    3 4\n    6 3\n    5 7\n    3 8\n    6 8\n    11 12\n    '))
	pp(string_source('200000 3\n    7 9\n    9 8\n    4 5'))
	if False:
		pass
else:
	pp(sys.stdin.readline)


from collections import defaultdict
import sys
import math
import typing

class DSU:

	def __init__(self, n: int=0) -> None:
		self._n = n
		self.parent_or_size = [-1] * n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a < self._n
		parent = self.parent_or_size[a]
		while parent >= 0:
			if self.parent_or_size[parent] < 0:
				return parent
			(self.parent_or_size[a], a, parent) = (self.parent_or_size[parent], self.parent_or_size[parent], self.parent_or_size[self.parent_or_size[parent]])
		return a

	def size(self, a: int) -> int:
		assert 0 <= a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self) -> typing.List[typing.List[int]]:
		leader_buf = [self.leader(i) for i in range(self._n)]
		result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		return list(filter(lambda r: r, result))

def input():
	return sys.stdin.readline().rstrip()

def slv():
	(n, m) = map(int, input().split())
	dsu = DSU(n)
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		dsu.merge(u, v)
	a = [dsu.leader(i) for i in range(n)]
	d = defaultdict(list)
	for i in range(n):
		d[dsu.leader(i)].append(i)
	ans = 0
	Groups = set([])
	for i in range(n):
		if not Groups:
			for node in d[dsu.leader(i)]:
				Groups.add(node)
		elif i not in Groups:
			ans += 1
			for node in d[dsu.leader(i)]:
				Groups.add(node)
		Groups.remove(i)
	print(ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


import sys
input = sys.stdin.buffer.readline

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def find_root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find_root(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find_root(x)
		y = self.find_root(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def size(self, x):
		return -self.root[self.find_root(x)]

def main():
	(n, m) = map(int, input().split())
	UF = UnionFind(n)
	edges = []
	for _ in range(m):
		(a, b) = map(int, input().split())
		UF.unite(a, b)
		(a, b) = (min(a, b), max(a, b))
		edges.append((a, b))
	edges.sort(key=lambda x: x[0])
	seen = -1
	ans = 0
	for (a, b) in edges:
		if seen < b:
			for c in range(max(seen + 1, a + 1), b):
				if not UF.isSameGroup(a, c):
					ans += 1
					UF.unite(a, c)
			seen = b
	print(ans)
main()


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

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	@bootstrap
	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = (yield self.DFSUtil(temp, i, visited))
		yield temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = []
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.DFSUtil(temp, v, visited))
		return cc
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
G = Graph(n)
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	G.addEdge(u, v)
c = G.connectedComponents()
dp = [0] * n
dp_1 = [0] * n
count = 0
total = 0
new = 0
for i in c:
	i.sort()
	dp[i[0]] += 1
	dp_1[i[-1]] += -1
for i in range(0, len(dp)):
	if dp[i] == 1:
		total += dp[i]
		count += 1
	if dp_1[i] == -1:
		total += dp_1[i]
		if total == 0:
			new = new + count - 1
			count = 0
print(new)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

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

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

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

	def group_count(self):
		return len(self.roots())
(n, m) = inpl()
uf = UnionFind(n)
se = set()
for _ in range(m):
	(a, b) = inpl()
	(a, b) = (a - 1, b - 1)
	se.add(a)
	se.add(b)
	uf.union(a, b)
d = {}
par = [[] for _ in range(n)]
for i in range(n):
	tmp = uf.find(i)
	par[tmp].append(i)
	d[i] = tmp
seg = []
for i in range(n):
	if par[i] == []:
		continue
	(a, b) = (min(par[i]), max(par[i]))
	seg.append((a, b))
seg.sort(key=lambda x: x[0])
res = 0
t = -1
for (a, b) in seg:
	if a < t:
		res += 1
	t = max(t, b)
print(res)


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
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')

def add(a, b):
	l[a].append(b)
	l[b].append(a)
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

@bootstrap
def find(u):
	global ma
	cur.add(u)
	ma = max(ma, u)
	for j in l[u]:
		if j not in cur:
			yield find(j)
	yield 0
(n, m) = map(int, input().split())
l = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	add(u, v)
ans = 0
j = 1
while j <= n:
	cur = set()
	ma = j
	find(j)
	k = j + 1
	while k < ma:
		if k not in cur:
			ans += 1
			find(k)
		k += 1
	j = ma + 1
print(ans)


(n, m) = map(int, input().split())
a = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	a[x].append(y)
	a[y].append(x)
vis = [1] * (n + 1)
c = 0
m = 1
for i in range(1, n + 1):
	if vis[i]:
		if i < m:
			c += 1
		s = [i]
		while s:
			x = s.pop()
			if vis[x]:
				s += a[x]
				vis[x] = 0
				if x > m:
					m = x
print(c)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict

def dfs(node):
	vis[node] = 1
	stack = [node]
	a = node
	b = node
	while stack:
		cur = stack.pop()
		for j in edge[cur]:
			if vis[j] == 0:
				a = min(a, j)
				b = max(b, j)
				stack.append(j)
				vis[j] = 1
	return (a, b)
(n, m) = list(map(int, input().split()))
edge = defaultdict(list)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	edge[u].append(v)
	edge[v].append(u)
vis = [0] * (n + 1)
arr1 = []
arr2 = []
x = 0
for i in range(1, n + 1):
	if vis[i] == 0:
		(a, b) = dfs(i)
		arr1.append(a)
		arr2.append(b)
		x += 1
ans = 0
maxi = 0
for i in range(x):
	if maxi > arr1[i]:
		ans += 1
	maxi = max(maxi, arr2[i])
print(ans)


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

def find(z, p):
	a = []
	while p[z] != z:
		a.append(z)
		z = p[z]
	for i in a:
		p[i] = z
	return z

def union(p, s, x, y):
	if s[x] >= s[y]:
		s[x] += s[y]
		p[y] = p[x]
	else:
		s[y] += s[x]
		p[x] = p[y]

def main():
	(n, m) = map(int, input().split())
	p = [i for i in range(n + 1)]
	s = [1] * (n + 1)
	for _ in range(m):
		(u, v) = map(int, input().split())
		(x, y) = (find(u, p), find(v, p))
		if x != y:
			union(p, s, x, y)
	for i in range(1, n + 1):
		p[i] = find(i, p)
	b = [0] * (n + 1)
	for i in range(n + 1):
		z = b[p[i]]
		if z:
			b[p[i]] = [z[0], i]
		else:
			b[p[i]] = [i, i]
	a = []
	for i in b:
		if i:
			a.append(i)
	a.sort(key=lambda x: x[0])
	(ans, u, v) = (0, 0, 0)
	for i in a:
		(u, v) = (max(u, i[0]), max(v, i[1]))
		for j in range(u, v):
			(x, y) = (find(j, p), find(j + 1, p))
			if x != y:
				union(p, s, x, y)
				ans += 1
		u = v
	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()


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.cnt = n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x != y:
			if self.parent[x] > self.parent[y]:
				(x, y) = (y, x)
			self.parent[x] += self.parent[y]
			self.parent[y] = x
			self.cnt -= 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def get_size(self, x):
		return -self.parent[self.root(x)]

	def get_cnt(self):
		return self.cnt
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
uf = UnionFind(n)
for (a, b) in info:
	uf.merge(a - 1, b - 1)
ans = 0
i = 0
while True:
	if i >= n:
		break
	cnt = uf.get_size(i)
	j = i
	while cnt:
		if uf.is_same(i, j):
			cnt -= 1
			j += 1
		else:
			cnt -= 1
			cnt += uf.get_size(j)
			ans += 1
			uf.merge(i, j)
			j += 1
	i = j
print(ans)


from sys import stdin
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline()
(n, e) = mi()
a = [[] for _ in range(n + 1)]
for _ in range(e):
	(x, y) = mi()
	a[x].append(y)
	a[y].append(x)
v = [1] * (n + 1)
c = 0
m = 1
for i in range(1, n + 1):
	if v[i]:
		s = [i]
		if i < m:
			c += 1
		while s != []:
			x = s.pop()
			if v[x]:
				s += a[x]
				v[x] = 0
				if x > m:
					m = x
print(c)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
(n, m) = map(int, input().split())
adj = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
v = [0] * (n + 1)
cmps = []
for i in range(1, n + 1):
	if not v[i]:
		mn_cmp = i
		mx_cmp = i
		q = [i]
		while q:
			e = q.pop()
			v[e] = 1
			mn_cmp = min(mn_cmp, e)
			mx_cmp = max(mx_cmp, e)
			for j in adj[e]:
				if not v[j]:
					q.append(j)
		cmps.append((mn_cmp, mx_cmp))
cmps.sort()
ans = 0
cur_mn = cmps[0][0]
cur_mx = cmps[0][1]
for i in range(1, len(cmps)):
	if cmps[i][0] < cur_mx:
		cur_mx = max(cur_mx, cmps[i][1])
		ans += 1
	else:
		cur_mn = cmps[i][0]
		cur_mx = cmps[i][1]
print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, m) = kk()
dsu = [i for i in range(n)]
maxs = [i for i in range(n)]

def find(a):
	a2 = a
	while dsu[a2] != a2:
		a2 = dsu[a2]
	while dsu[a] != a:
		(dsu[a], a) = (a2, dsu[a])
	return a

def same(a, b):
	return find(a) == find(b)

def union(a, b):
	(a, b) = (find(a), find(b))
	dsu[a] = b
	maxs[b] = max(maxs[a], maxs[b])
for _ in range(m):
	(a, b) = kk()
	union(a - 1, b - 1)
i = 0
ans = 0
while i < n:
	x = find(i)
	while i < maxs[x]:
		d2 = find(i)
		if d2 != x:
			ans += 1
			union(d2, x)
		i += 1
	i += 1
print(ans)


class DisjointSetUnion:

	def __init__(self, n):
		self.parent = [*range(n + 1)]
		self.size = [1] * (n + 1)
		(self.min, self.max) = ([*range(n + 1)], [*range(n + 1)])
		self.count = n

	def get(self, a):
		if self.parent[a] == a:
			return a
		x = a
		while a != self.parent[a]:
			a = self.parent[a]
		while x != self.parent[x]:
			(self.parent[x], x) = (a, self.parent[x])
		return a

	def union(self, a, b):
		(a, b) = (self.get(a), self.get(b))
		if a != b:
			if self.size[a] > self.size[b]:
				(a, b) = (b, a)
			self.parent[a] = b
			self.size[b] += self.size[a]
			self.min[b] = min(self.min[a], self.min[b])
			self.max[b] = max(self.max[a], self.max[b])
			self.count -= 1

	def count_sets(self):
		return self.count
import os
import sys
from io import BytesIO, IOBase
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 math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
	(components, visited) = ([], [False] * n)

	def dfs(start):
		(component, stack) = ([], [start])
		while stack:
			start = stack[-1]
			if visited[start]:
				stack.pop()
				continue
			else:
				visited[start] = True
				component.append(start)
			for i in graph[start]:
				if not visited[i]:
					stack.append(i)
		return component
	for i in range(n):
		if not visited[i]:
			components.append(dfs(i))
	return components
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
	cc = connected_components(n + 1, graph)
	cc = sorted([[min(k), max(k)] for k in cc])
	ans = 0
	mx = 0
	for (alpha, omega) in cc:
		if alpha <= mx:
			ans += 1
		mx = max(mx, omega)
	print(ans - 1)


(n, m) = map(int, input().split())
graph = [list() for i in range(n + 1)]
visited = [False for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	graph[v].append(u)
	graph[u].append(v)
ans = 0
count = m = 1
stack = [count]
while count <= n:
	while len(stack) > 0:
		v = stack.pop()
		visited[v] = True
		m = max(v, m)
		for e in graph[v]:
			if not visited[e]:
				stack.append(e)
				visited[e] = True
	while count <= n and visited[count]:
		count += 1
	if count <= m:
		ans += 1
	stack.append(count)
print(ans)