One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles.

At the end of the day there were n castles built by friends. Castles are numbered from 1 to n, and the height of the i-th castle is equal to h_{i}. When friends were about to leave, Squidward noticed, that castles are not ordered by their height, and this looks ugly. Now friends are going to reorder the castles in a way to obtain that condition h_{i} ≤ h_{i} + 1 holds for all i from 1 to n - 1.

Squidward suggested the following process of sorting castles:   Castles are split into blocks — groups of consecutive castles. Therefore the block from i to j will include castles i, i + 1, ..., j. A block may consist of a single castle.  The partitioning is chosen in such a way that every castle is a part of exactly one block.  Each block is sorted independently from other blocks, that is the sequence h_{i}, h_{i} + 1, ..., h_{j} becomes sorted.  The partitioning should satisfy the condition that after each block is sorted, the sequence h_{i} becomes sorted too. This may always be achieved by saying that the whole sequence is a single block. 

Even Patrick understands that increasing the number of blocks in partitioning will ease the sorting process. Now friends ask you to count the maximum possible number of blocks in a partitioning that satisfies all the above requirements.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of castles Spongebob, Patrick and Squidward made from sand during the day.

The next line contains n integers h_{i} (1 ≤ h_{i} ≤ 10^9). The i-th of these integers corresponds to the height of the i-th castle.


-----Output-----

Print the maximum possible number of blocks in a valid partitioning.


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

Output
3

Input
4
2 1 3 2

Output
2



-----Note-----

In the first sample the partitioning looks like that: [1][2][3].

 [Image] 

In the second sample the partitioning is: [2, 1][3, 2]

 [Image]

Difficulty: MEDIUM_HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
n = int(input())
h = [int(x) for x in input().split()]
highest = []
lowest = []
max_until = 0
for i in range(0, n):
	max_until = max(max_until, h[i])
	highest.append(max_until)
min_until = 10 ** 9
for i in range(n - 1, 0 - 1, -1):
	min_until = min(min_until, h[i])
	lowest.append(min_until)
lowest.reverse()
parts = 1
for i in range(0, n - 1):
	if highest[i] <= lowest[i + 1]:
		parts += 1
print(parts)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
h = list(map(int, input().split()))
hWithIndex = []
for i in range(n):
	hWithIndex.append((i, h[i]))
hWithIndex.sort(key=lambda x: x[1])
originalToSorted = [0] * n
sortedToOriginal = [0] * n
for i in range(n):
	sortedToOriginal[i] = hWithIndex[i][0]
	originalToSorted[hWithIndex[i][0]] = i
currentIndex = 0
currentMax = 0
blocks = 0
while True:
	if currentIndex >= n:
		break
	blocks += 1
	updateMax = currentIndex
	updateIndex1 = currentIndex
	updateIndex2 = currentIndex
	while True:
		for i in range(updateIndex1, currentMax + 1):
			if updateMax < originalToSorted[i]:
				updateMax = originalToSorted[i]
		if updateMax == currentMax:
			break
		updateIndex1 = currentMax + 1
		currentMax = updateMax
		for i in range(updateIndex2, currentMax + 1):
			if updateMax < sortedToOriginal[i]:
				updateMax = sortedToOriginal[i]
		if updateMax == currentMax:
			break
		updateIndex2 = currentMax + 1
		currentMax = updateMax
	currentIndex = updateMax + 1
print(blocks)


n = int(input())
hs = tuple((int(x) for x in input().split()))

def blocks(seq):
	res = 0
	i = 0
	maxh = 0
	while True:
		if i == len(seq):
			return res
		maxh = max(maxh, seq[i])
		if maxh == i:
			res += 1
			i += 1
		elif maxh > i:
			i += 1

def solve(n, hs):
	hhs = sorted(((hs[i], i) for i in range(n)))
	hhhs = sorted(((i, hhs[i][0], hhs[i][1]) for i in range(n)))
	return blocks(list((h[1] for h in hhs)))
print(solve(n, hs))


__author__ = 'MoonBall'
import sys
T = 1

def process():
	N = int(input())
	h = map(int, input().split())
	hpx = []
	last = {}
	for (i, v) in enumerate(h):
		hpx.append([v, i])
	hpx = sorted(hpx, key=lambda x: x[0])
	maxp = -1
	i = 0
	while i < N:
		item = hpx[i]
		v = item[0]
		j = i
		while j < N and hpx[j][0] == v:
			p = hpx[j][1]
			last[p] = max(maxp, p)
			j = j + 1
		j = i
		while j < N and hpx[j][0] == v:
			p = hpx[j][1]
			maxp = max(maxp, p)
			j = j + 1
		i = j
	ans = 0
	p = 0
	while p < N:
		ans = ans + 1
		nextp = p + 1
		while p < N and p < nextp:
			nextp = max(nextp, last[p] + 1)
			p = p + 1
	print(ans)
for _ in range(T):
	process()


import itertools as it
import functools
import operator
import collections
import math
import sys

def solve(xs, n):
	max_upto = list(it.accumulate(xs, max))
	min_after = list(it.accumulate(reversed(xs), min))
	min_after.reverse()
	count = 1 + sum((1 for i in range(1, n) if max_upto[i - 1] <= min_after[i]))
	return count

def solve_old(xs, n):
	max_upto = []
	maxval = 0
	for x in xs:
		maxval = max(maxval, x)
		max_upto.append(maxval)
	min_after = []
	minval = 10000000000
	for x in reversed(xs):
		minval = min(minval, x)
		min_after.append(minval)
	min_after.reverse()
	count = 1
	for i in range(1, n):
		if max_upto[i - 1] <= min_after[i]:
			count += 1
	return count

def main():
	n = int(input())
	xs = [int(_c) for _c in input().strip().split()]
	result = solve(xs, n)
	print(result)

def __starting_point():
	main()
__starting_point()


n = int(input())
hs = list(map(int, input().split()))

def solve(n, hs):
	mins = fill_mins(n, hs)
	maxs = fill_maxs(n, hs)
	count = 1
	for i in range(n - 1):
		if maxs[i] <= mins[i + 1]:
			count += 1
	return count

def fill_mins(n, hs):
	mins = []
	tmp = float('inf')
	for h in hs[::-1]:
		if h < tmp:
			tmp = h
		mins.append(tmp)
	mins.reverse()
	return mins

def fill_maxs(n, hs):
	maxs = []
	tmp = 0
	for h in hs:
		if h > tmp:
			tmp = h
		maxs.append(tmp)
	return maxs
print(solve(n, hs))


import sys
n = int(input())
a = list(map(int, input().split()))
mn = [10000000000 for i in range(n + 2)]
for i in range(n - 1, -1, -1):
	mn[i] = min(mn[i + 1], a[i])
curmax = 0
ans = 0
for i in range(n):
	curmax = max(a[i], curmax)
	if curmax <= mn[i + 1]:
		ans += 1
		curmax = 0
print(ans)


(n, s, v) = (int(input()), 0, 0)
a = list(map(int, input().split()))
for (ai, bi) in zip(a, sorted(a)):
	s += bi - ai
	v += not s
print(v)


n = int(input())
arr = list(map(int, input().split()))
pref = []
suf = []
mx = -1
for i in range(n):
	if arr[i] > mx:
		mx = arr[i]
	pref.append(mx)
arr.reverse()
mn = 10000000000
for i in range(n):
	if arr[i] < mn:
		mn = arr[i]
	suf.append(mn)
suf.reverse()
arr.reverse()
answer = 0
for i in range(n - 1):
	if pref[i] <= suf[i + 1]:
		answer += 1
print(answer + 1)


n = int(input())
h = list(map(int, input().split()))
ind = [i for i in range(len(h))]
h = list(zip(h, ind))
h.sort()
ans = 0
m = 0
for i in range(len(h)):
	m = max(m, h[i][1])
	if m == i:
		ans += 1
print(ans)


def solve(h, n):
	sortedH = sorted(h)
	hsum = [0]
	for i in range(1, n + 1):
		hsum.append(hsum[i - 1] + sortedH[i - 1])
	tsum = 0
	start = 0
	res = 0
	for (i, hi) in enumerate(h):
		tsum += hi
		if tsum == hsum[i + 1] - hsum[start]:
			res += 1
			tsum = 0
			start = i + 1
	return res
n = int(input())
h = [int(x) - 1 for x in input().split()]
print(solve(h, n))


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):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
n = int(input())
h = list(map(int, input().split()))
uf = UnionFind(n)
h2 = []
for i in range(n):
	h2.append([i, h[i]])
h2 = sorted(h2, key=lambda student: (student[1], student[0]))
for i in range(n):
	l = min(i, h2[i][0])
	r = max(i, h2[i][0])
	for j in range(l, r):
		if uf.same(j, r):
			break
		uf.union(j, j + 1)
print(uf.group_count())


n = int(input())
h = list(map(int, input().split()))
mins = [1000000001 for i in range(n)]
maxs = [0 for i in range(n)]
ans = 0
mins[n - 1] = h[n - 1]
for i in range(n - 2, -1, -1):
	mins[i] = min(h[i], mins[i + 1])
maxs[0] = h[0]
for i in range(1, n):
	maxs[i] = max(maxs[i - 1], h[i])
for i in range(n - 1):
	if maxs[i] <= mins[i + 1]:
		ans += 1
print(ans + 1)


from collections import Counter as Cnt
n = int(input())
data = tuple(map(int, input().split()))
datasorted = sorted(data)
i = 0
a = Cnt()
b = Cnt()
ans = 0
for i in range(n):
	a[data[i]] += 1
	b[datasorted[i]] += 1
	if a == b:
		ans += 1
		(a, b) = (Cnt(), Cnt())
print(ans)


n = int(input())
hs = list(map(int, input().split()))
max_h = 0
rs = []
max_hs = [0] * n
for (i, h) in enumerate(hs):
	rs.append((h, i))
	max_h = max(max_h, h)
	max_hs[i] = max_h
rs.sort()
(p, r) = (0, -1)
ans = 0
while r < n - 1:
	(nh, nr) = rs[p]
	if r >= nr:
		p += 1
	else:
		r = nr
		p += 1
		while r < n - 1:
			(nh, nr) = rs[p]
			if nh >= max_hs[r]:
				break
			r = max(r, nr)
			p += 1
		ans += 1
print(ans)


def binsearch(a, x, k):
	l = 0
	r = k
	while l < r - 1:
		m = (l + r) // 2
		if a[m] <= x:
			l = m
		else:
			r = m
	return l
n = int(input())
k = -1
a = [0] * n
for i in input().split():
	x = int(i)
	if k == -1:
		k += 1
		a[k] = x
	elif x >= a[k]:
		k += 1
		a[k] = x
	else:
		k1 = k
		k = binsearch(a, x, k + 1)
		if a[k] <= x:
			k += 1
		a[k] = a[k1]
print(k + 1)


from sys import stdin, stdout
from collections import defaultdict
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	a = list(zip(lst(), range(n)))
	a.sort()
	ans = mx = 0
	for i in range(n):
		mx = max(a[i][1], mx)
		if mx == i:
			ans += 1
	print(ans)


q = input()
a = list(map(int, input().split()))
s = 0
w = 0
for (i, j) in zip(a, sorted(a)):
	s += j - i
	w += not s
print(w)


import sys

def main():
	n = int(input())
	h = list(map(int, sys.stdin.readline().split()))
	h = [0] + h
	hmax = [0] * (n + 1)
	hmin = [0] * (n + 1)
	hmax[1] = h[1]
	hmin[n] = h[n]
	for i in range(2, n + 1):
		hmax[i] = max(hmax[i - 1], h[i])
	for i in range(n - 1, 0, -1):
		hmin[i] = min(hmin[i + 1], h[i])
	s = 1
	for i in range(1, n):
		if hmax[i] <= hmin[i + 1]:
			s += 1
	print(s)
main()


def arr_enu():
	return sorted(list(([i, int(x)] for (i, x) in enumerate(stdin.readline().split()))), key=itemgetter(1, 0))
from sys import stdin
from collections import *
from operator import itemgetter
(n, a) = (int(input()), arr_enu())
(ans, l, ma, mi) = (0, 0, 0, 0)
for i in range(n):
	ma = max(ma, a[i][0])
	l += 1
	if l == ma - mi + 1:
		(mi, l, ma) = (i + 1, 0, i + 1)
		ans += 1
print(ans)


x = int(input())
y = list(map(int, input().split(' ')))
z = y[:]
z.sort()
sumx = 0
sumx2 = 0
b = 0
for i in range(x):
	sumx += y[i]
	sumx2 += z[i]
	if sumx == sumx2:
		b += 1
print(b)


n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
(curr_diff, res, cnt) = (0, 0, {})
for i in range(n):
	if a[i] not in cnt:
		cnt[a[i]] = 0
	if b[i] not in cnt:
		cnt[b[i]] = 0
	cnt[a[i]] += 1
	if cnt[a[i]] == 1:
		curr_diff += 1
	if cnt[a[i]] == 0:
		curr_diff -= 1
	if cnt[b[i]] == 0:
		curr_diff += 1
	if cnt[b[i]] == 1:
		curr_diff -= 1
	cnt[b[i]] -= 1
	if curr_diff == 0:
		res += 1
print(res)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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 value():
	return tuple(map(int, input().split()))

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

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = array()
sorted_a = sorted(a)
pre = [sorted_a[0]]
for i in range(1, n):
	pre.append(pre[-1] + sorted_a[i])
blocks = 0
cur = 0
for i in range(n):
	cur += a[i]
	if cur == pre[i]:
		blocks += 1
print(blocks)


n = int(input())
l = list(map(int, input().split()))
k = sorted(l)
ans = 0
x = 0
for t in range(n):
	x += k[t] - l[t]
	if x == 0:
		ans += 1
print(ans)


def get_segments(hs, positions):
	for (i, h) in enumerate(hs):
		j = positions[h]
		positions[h] += 1
		if i > j:
			(i, j) = (j, i)
		yield (i, j)

def merge_segments(segments):
	(ci, cj) = (None, None)
	for (i, j) in sorted(segments):
		if ci is None:
			(ci, cj) = (i, j)
		elif i > cj:
			yield (ci, cj)
			(ci, cj) = (i, j)
		else:
			cj = max(cj, j)
	yield (ci, cj)

def max_partition(n, hs):
	seq = sorted(hs)
	positions = {seq[i]: i for i in range(n) if not (i > 0 and seq[i - 1] == seq[i])}
	return sum((1 for _ in merge_segments(get_segments(hs, positions))))
n = int(input())
hs = tuple(map(int, input().split()))
print(max_partition(n, hs))


n = int(input())
hh = list(map(int, input().split()))
idx = sorted(range(n), key=lambda i: hh[i])
num_blocks = 0
curr_max = idx[0]
for (j, i) in enumerate(idx):
	curr_max = max(i, curr_max)
	if curr_max <= j:
		num_blocks += 1
print(num_blocks)


from operator import itemgetter
n = int(input())
inp = [int(i) for i in input().split()]
ori = [[inp[i], i] for i in range(len(inp))]
sorted_ori = sorted(ori, key=itemgetter(0, 1))
(pivot, ans) = (-1, 0)
for i in range(n):
	pivot = max(sorted_ori[i][1], pivot)
	if pivot == i:
		ans = ans + 1
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int, input().split()))
acc_min = [10 ** 18]
for hi in h[::-1]:
	acc_min.append(min(acc_min[-1], hi))
acc_min = acc_min[::-1]
now_max = 0
ans = 0
for i in range(n):
	now_max = max(now_max, h[i])
	if now_max <= acc_min[i + 1]:
		ans += 1
		now_max = 0
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
pref = [0] * (n + 1)
for i in range(n):
	pref[i + 1] = max(pref[i], a[i])
suff = [0] * n
suff[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
	suff[i] = min(suff[i + 1], a[i])
c = 0
for i in range(n):
	if pref[i] <= suff[i]:
		c += 1
print(c)


from collections import defaultdict
dic = defaultdict(list)
n = int(input())
li = list(map(int, input().split()))
sortedLi = sorted(li)
for i in range(n):
	dic[sortedLi[i]].append(i)
common = []
for idx in range(n):
	common.append(sorted((idx, dic[li[idx]][0])))
	dic[li[idx]].pop(0)
ans = 1
counted = False
tempEdge = common[0][1]
for i in range(len(common)):
	if common[i][0] > tempEdge:
		ans += 1
	if common[i][1] > tempEdge:
		tempEdge = common[i][1]
print(ans)


from collections import Counter
n = int(input())
h_u = tuple(map(int, input().split()))
h_s = sorted(h_u)
i = 0
a = Counter()
b = Counter()
num_partitions = 0
for i in range(n):
	a[h_u[i]] += 1
	b[h_s[i]] += 1
	if a == b:
		num_partitions += 1
		a = Counter()
		b = Counter()
print(num_partitions)


import sys
from collections import defaultdict
n = int(input())
a = [int(v) for v in sys.stdin.readline().split()]
b = a[:]
b.sort()
q = 0
c = 0
d = defaultdict(list)
for j in range(n):
	d[b[j]].append(j)
for j in range(n):
	p = d[a[j]][0]
	del d[a[j]][0]
	q = q + j - p
	if q == 0:
		c = c + 1
print(c)


R = lambda : map(int, input().split())
n = int(input())
heights = list(R())
sorted_heights = sorted(heights[:])
from collections import deque
d = {}
for (i, hi) in enumerate(sorted_heights, 0):
	if hi not in d:
		d[hi] = deque()
	d[hi].append(i)
s = set()
mhs = 0
res = 0
for hi in heights:
	i = d[hi].popleft()
	mhs = max(mhs, i)
	s.add(i)
	if mhs == len(s) - 1:
		res += 1
print(res)


def res(inp):
	mn = [None] * len(inp)
	mx = [None] * len(inp)
	n = len(inp)
	_mn = 10 ** 10
	_mx = -1
	for i in range(n):
		ri = n - i - 1
		_mn = min(_mn, inp[ri])
		mn[ri] = _mn
		_mx = max(_mx, inp[i])
		mx[i] = _mx
	r = 0
	for i in range(len(inp) - 1):
		if mx[i] <= mn[i + 1]:
			r += 1
	return r + 1
l = int(input())
inp = tuple(map(int, input().split()))
print(res(inp))


n = int(input())
a = list(map(int, input().split()))
s = 0
cnt = 0
for (ai, bi) in zip(a, sorted(a)):
	s += bi - ai
	if s == 0:
		cnt += 1
print(cnt)


n = int(input())
h = [int(i) for i in input().split(' ')]
mini = h[0]
maxi = h[0]
group = [[mini, maxi]]
for i in range(n):
	if h[i] < group[-1][1]:
		group[-1][0] = h[i]
		while len(group) > 2 and group[-1][0] < group[-2][1]:
			group[-1][1] = max(group[-1][1], group[-2][1])
			group.pop(-2)
	elif h[i] >= group[-1][1]:
		group.append([h[i], h[i]])
print(len(group) - 1)


def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	b = sorted(a)
	diff = 0
	d = {}
	result = 0
	maxi = 0
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = 0
		if b[i] not in d:
			d[b[i]] = 0
		if d[a[i]] == 0:
			diff += 1
		d[a[i]] += 1
		if d[a[i]] == 0:
			diff -= 1
		if d[b[i]] == 0:
			diff += 1
		d[b[i]] -= 1
		if d[b[i]] == 0:
			diff -= 1
		if diff == 0:
			result += 1
	print(result)
main()


__author__ = 'sandeepmellacheruvu'
n = int(input())
arr = list(map(int, input().split()))
sum = 0
blocks = 0
for (ai, bi) in zip(arr, sorted(arr)):
	sum += ai - bi
	if sum == 0:
		blocks += 1
print(blocks)


n = int(input())
h = list(map(int, input().split()))
h1 = h[:]
h1.sort()
s1 = 0
s2 = 0
part = 0
for i in range(n):
	s1 += h[i]
	s2 += h1[i]
	if s1 == s2:
		part += 1
print(part)


from collections import Counter
n = int(input())
data = list(map(int, input().split()))
dd = {}
for (i, x) in enumerate(sorted(data)):
	if x not in dd:
		dd[x] = i
m = None
c = 0
n_pos = None
counter = Counter()
for (i, x) in enumerate(data):
	if n_pos is None:
		if dd[x] + counter[x] == i:
			c += 1
		else:
			n_pos = dd[x] + counter[x]
			m = x
	else:
		if x >= m:
			m = x
			n_pos = dd[x] + counter[x]
		if i == n_pos:
			c += 1
			n_pos = None
	counter[x] += 1
print(c)


n = int(input())
given = list(map(int, input().split()))
maxes = n * [None]
maxes[0] = given[0]
for i in range(1, n):
	maxes[i] = max(maxes[i - 1], given[i])
result = 1
min_now = given[n - 1]
for i in range(n - 1, 0, -1):
	min_now = min(min_now, given[i])
	if maxes[i - 1] <= min_now:
		result += 1
print(result)


n = int(input())
s = input().split()
a = [[0] * 2 for i in range(n)]
for i in range(n):
	a[i][0] = int(s[i])
	a[i][1] = i
a.sort()
if a[0][1] == n - 1 or a[n - 1][1] == 0:
	print(1)
else:
	sum = 0
	res = 0
	ans = 0
	for i in range(n):
		sum += a[i][1]
		res += i
		if sum == res:
			ans += 1
	print(ans)


n = int(input())
h = list(map(int, input().split()))
premax = [0] * n
premax[0] = h[0]
for i in range(1, n):
	premax[i] = max(h[i], premax[i - 1])
suffmin = [0] * n
suffmin[-1] = h[-1]
for i in range(n - 1)[::-1]:
	suffmin[i] = min(h[i], suffmin[i + 1])
ans = 1
for i in range(n - 1):
	if premax[i] <= suffmin[i + 1]:
		ans += 1
print(ans)


mod = 10 ** 9 + 7
x = int(input())
y = list(map(int, input().split(' ')))
z = y[:]
z.sort()
prod = 1
sumx = 0
prod2 = 1
sumx2 = 0
b = 0
for i in range(x):
	prod *= y[i]
	sumx += y[i]
	prod2 *= z[i]
	sumx2 += z[i]
	prod %= mod
	prod2 %= mod
	if prod == prod2 and sumx == sumx2:
		b += 1
		prod = 1
		prod2 = 1
		sumx = 0
		sumx2 = 0
print(b)


n = int(input())
s = 0
v = 0
a = list(map(int, input().split()))
for (i, j) in zip(a, sorted(a)):
	s += i - j
	v += not s
print(v)


import unittest
import sys

class Beach:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.n] = list(map(int, uinput().split()))
		self.nums = list(map(int, uinput().split()))

	def calculate(self):
		(result, u) = (0, 0)
		tp = sorted([(n, i) for (i, n) in enumerate(self.nums)])
		for i in range(self.n):
			u = max(u, tp[i][1])
			if i >= u:
				result += 1
		return str(result)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '3\n1 2 3'
		d = Beach(test)
		self.assertEqual(d.n, 3)
		self.assertEqual(d.nums, [1, 2, 3])
		self.assertEqual(Beach(test).calculate(), '3')
		test = '4\n2 1 3 2'
		self.assertEqual(Beach(test).calculate(), '2')
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Beach(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))

def __starting_point():
	sys.setrecursionlimit(100000)
	if sys.argv[-1] == '-ut':
		unittest.main(argv=[' '])
	sys.stdout.write(Beach().calculate())
__starting_point()


n = int(input())
given = list(map(int, input().split()))
target = sorted(given)
result = 0
pos = 0
while pos < n:
	result += 1
	min_value_given = max_value_given = given[pos]
	min_count_given = max_count_given = 1
	min_value_target = max_value_target = target[pos]
	min_count_target = max_count_target = 1
	while min_value_given != min_value_target or min_count_given != min_count_target or max_value_given != max_value_target or (max_count_given != max_count_target):
		pos += 1
		if pos == n:
			break
		(g, t) = (given[pos], target[pos])
		if g < min_value_given:
			min_value_given = g
			min_count_given = 1
		elif g == min_value_given:
			min_count_given += 1
		if g > max_value_given:
			max_value_given = g
			max_count_given = 1
		elif g == max_value_given:
			max_count_given += 1
		if t < min_value_target:
			min_value_target = t
			min_count_target = 1
		elif t == min_value_target:
			min_count_target += 1
		if t > max_value_target:
			max_value_target = t
			max_count_target = 1
		elif t == max_value_target:
			max_count_target += 1
	pos += 1
print(result)


from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
sorted_arr = sorted(arr)
pos_d = defaultdict(list)
for (i, el) in enumerate(sorted_arr):
	if el in pos_d:
		pos_d[el][1] = i
	else:
		pos_d[el] = [i, i]
num_seen = 0
curr_pos = defaultdict(int)

def get_position(el):
	if el in curr_pos:
		pos = curr_pos[el]
		curr_pos[el] = pos + 1
	else:
		pos = pos_d[el][0]
		curr_pos[el] = pos + 1
	return pos
max_position = 0
for (i, el) in enumerate(arr):
	position = get_position(el)
	max_position = max(max_position, position)
	if i == max_position:
		num_seen += 1
print(num_seen)


n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = {}
d = {}
e = 0
for i in range(n):
	if a[i] not in c.keys():
		c[a[i]] = 1
	else:
		c[a[i]] += 1
	if b[i] not in d.keys():
		d[b[i]] = 1
	else:
		d[b[i]] += 1
	if c == d:
		e = e + 1
		c = {}
		d = {}
print(e)


from collections import Counter

def mp():
	return map(int, input().split())

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

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def printlist(l):
	print(' '.join([str(x) for x in l]))
n = it()
prefix = 0
result = 0
a = lt()
for (x, y) in zip(a, sorted(a)):
	prefix += x - y
	if prefix == 0:
		result += 1
print(result)


def solve(lst):
	pre = []
	m = -float('inf')
	for num in lst:
		m = max(m, num)
		pre.append(m)
	post = [None] * len(lst)
	m = float('inf')
	for i in reversed(range(len(lst))):
		m = min(lst[i], m)
		post[i] = m
	count = 0
	for i in range(len(lst) - 1):
		if pre[i] <= post[i + 1]:
			count += 1
	return count + 1
n = input()
lst = list(map(int, input().split()))
print(solve(lst))


from collections import Counter
n = int(input())
H = list(map(int, input().split()))
_H = sorted(H)
diff = Counter()
count = 0
for i in range(n):
	diff[H[i]] += 1
	diff[_H[i]] -= 1
	if _H[i] in diff and diff[_H[i]] == 0:
		diff.pop(_H[i])
	if H[i] in diff and diff[H[i]] == 0:
		diff.pop(H[i])
	if diff == Counter():
		count += 1
print(count)


def main():
	(n, l) = (int(input()), list(map(int, input().split())))
	res = m = 0
	for (i, x) in enumerate(sorted(range(n), key=l.__getitem__)):
		if m < x:
			m = x
		if m == i:
			res += 1
	print(res)
main()


n = int(input())
h = list(map(int, input().split()))
sorted_h = list(h)
sorted_h.sort()
a = {}
b = {}
answer = 0
for i in range(n):
	if sorted_h[i] in a:
		a[sorted_h[i]] += 1
	else:
		a[sorted_h[i]] = 1
	if h[i] in b:
		b[h[i]] += 1
	else:
		b[h[i]] = 1
	if a == b:
		answer += 1
		a = {}
		b = {}
print(answer)


from sys import stdin, stdout
from collections import defaultdict
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	a = lst()
	g = defaultdict(list)
	ptr = {v: 0 for v in a}
	b = sorted(a)
	for i in range(n):
		g[b[i]] += [i]
	ans = 0
	mp = -1
	for i in range(n):
		cur_pt = g[a[i]][ptr[a[i]]]
		ptr[a[i]] += 1
		mp = max(mp, cur_pt)
		if i == mp:
			ans += 1
			mp = -1
	print(ans)


def maxPartitions(N, array):
	preMax = [0] * N
	sufMin = [0] * N
	preMax[0] = array[0]
	max_so_far = array[0]
	i = 1
	while i < N:
		preMax[i] = max(array[i], max_so_far)
		max_so_far = max(array[i], max_so_far)
		i += 1
	sufMin[N - 1] = array[N - 1]
	min_so_far = array[N - 1]
	i = N - 2
	while i >= 0:
		sufMin[i] = min(array[i], min_so_far)
		min_so_far = min(array[i], min_so_far)
		i -= 1
	total = 0
	for i in range(N - 1):
		if preMax[i] <= sufMin[i + 1]:
			total += 1
	if preMax[N - 1] == max_so_far:
		total += 1
	return total
N = int(input())
array = input().split()
array = [int(x) for x in array]
print(maxPartitions(N, array))


import math, sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda : int(input())
li = lambda : list(map(int, input().split()))

def case():
	n = I()
	a = li()
	b = a.copy()
	b.sort()
	d = defaultdict(int)
	j = 0
	ans = 0
	for i in range(n):
		if a[i] == b[j]:
			d[b[j]] += 1
			while j < n and b[j] in d:
				d[b[j]] -= 1
				if d[b[j]] == 0:
					del d[b[j]]
				j += 1
				if j == i + 1:
					ans += 1
					break
		else:
			d[a[i]] += 1
	print(ans)
for _ in range(1):
	case()