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: interview

Starter code:

Solutions:
#!/usr/bin/env python3

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)

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)

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

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

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

def __starting_point():

    n = int( input() )
    h = [ int(x)-1 for x in input().split() ]

    print( solve( h , n ) )
__starting_point()

from collections import Counter

def __starting_point():
    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)

__starting_point()

"""
Codeforces Round 332

Problem 599 C.

@author yamaton
@date 2015-11-20
"""

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



def solve(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


#
# @functools.lru_cache(maxsize=None)
# def count(tup):
#     if len(tup) == 1:
#         return 1
#
#     maxval = 1
#     n = len(tup)
#     for i in range(1, n):
#         first = tup[:i]
#         second = tup[i:]
#         if max(first) <= min(second):
#             maxval = max(maxval, count(first) + count(second))
#     return maxval
#
#
# def solve(xs, n):
#     return count(tuple(xs))


# def p(*args, **kwargs):
#     return print(*args, file=sys.stderr, **kwargs)


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

__author__ = 'MoonBall'

import sys
# sys.stdin = open('data/C.in', 'r')
T = 1

def process():
    N = int(input())
    h = list(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()


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)
    
    


n = int(input())
hs = list(map(int, input().split()))
chs = list(set(hs))
chs.sort()
rchs = {}
for i, v in enumerate(chs):
    rchs[v] = i
for i in range(n):
    hs[i] = rchs[hs[i]]
max_h = -1
rs = []
max_hs = [0] * n
for i, h in enumerate(hs):
    max_h = max(max_h, h)
    rs.append((h, i))
    max_hs[i] = max_h
rs.sort()
h, r = 0, -1
p = 0
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)


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)


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)

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)

x = int(input())
y = list(map(int, input().split(' ')))
z = y[:]
z.sort()
sumx = 0
b = 0

for i in range(x):
    sumx += y[i] - z[i]
    if (sumx == 0):
        b+=1

print(b)

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)


"""
Codeforces Round #332

Problem 599 C. Day at the Beach

@author yamaton
@date 2015-11-20
"""

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


#
# @functools.lru_cache(maxsize=None)
# def count(tup):
#     if len(tup) == 1:
#         return 1
#
#     maxval = 1
#     n = len(tup)
#     for i in range(1, n):
#         first = tup[:i]
#         second = tup[i:]
#         if max(first) <= min(second):
#             maxval = max(maxval, count(first) + count(second))
#     return maxval
#
#
# def solve(xs, n):
#     return count(tuple(xs))


# def p(*args, **kwargs):
#     return print(*args, file=sys.stderr, **kwargs)


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

#!/usr/bin/env python3
# 599C_beach.py - Codeforces.com/problemset/problem/599/C by Sergey 2015

import unittest
import sys

###############################################################################
# Beach Class (Main Program)
###############################################################################


class Beach:
    """ Beach representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        [self.n] = list(map(int, uinput().split()))

        # Reading a single line of multiple elements
        self.nums = list(map(int, uinput().split()))

    def calculate(self):
        """ Main calcualtion function of the class """

        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)

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Beach class testing """

        # Constructor test
        test = "3\n1 2 3"
        d = Beach(test)
        self.assertEqual(d.n, 3)
        self.assertEqual(d.nums, [1, 2, 3])

        # Sample test
        self.assertEqual(Beach(test).calculate(), "3")

        # Sample test
        test = "4\n2 1 3 2"
        self.assertEqual(Beach(test).calculate(), "2")

        # My tests
        test = ""
        # self.assertEqual(Beach(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        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"

        # Run the test
        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():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Beach().calculate())

__starting_point()

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)

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
    else:
        if 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)

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

# import sys
# sys.stdin = open('cf599c.in')

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)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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)


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[2] for h in hhhs)) 
    
print(solve(n, hs))