Emuskald is addicted to Codeforces, and keeps refreshing the main page not to miss any changes in the "recent actions" list. He likes to read thread conversations where each thread consists of multiple messages.

Recent actions shows a list of n different threads ordered by the time of the latest message in the thread. When a new message is posted in a thread that thread jumps on the top of the list. No two messages of different threads are ever posted at the same time.

Emuskald has just finished reading all his opened threads and refreshes the main page for some more messages to feed his addiction. He notices that no new threads have appeared in the list and at the i-th place in the list there is a thread that was at the a_{i}-th place before the refresh. He doesn't want to waste any time reading old messages so he wants to open only threads with new messages.

Help Emuskald find out the number of threads that surely have new messages. A thread x surely has a new message if there is no such sequence of thread updates (posting messages) that both conditions hold:   thread x is not updated (it has no new messages);  the list order 1, 2, ..., n changes to a_1, a_2, ..., a_{n}. 


-----Input-----

The first line of input contains an integer n, the number of threads (1 ≤ n ≤ 10^5). The next line contains a list of n space-separated integers a_1, a_2, ..., a_{n} where a_{i} (1 ≤ a_{i} ≤ n) is the old position of the i-th thread in the new list. It is guaranteed that all of the a_{i} are distinct.


-----Output-----

Output a single integer — the number of threads that surely contain a new message.


-----Examples-----
Input
5
5 2 1 3 4

Output
2

Input
3
1 2 3

Output
0

Input
4
4 3 2 1

Output
3



-----Note-----

In the first test case, threads 2 and 5 are placed before the thread 1, so these threads must contain new messages. Threads 1, 3 and 4 may contain no new messages, if only threads 2 and 5 have new messages.

In the second test case, there may be no new messages at all, since the thread order hasn't changed.

In the third test case, only thread 1 can contain no new messages.

Difficulty: MEDIUM
Tags: Data structures

Implementation

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
__author__ = 'asmn'
n = int(input())
a = list(reversed(list(map(int, input().split()))))
for i in range(1, len(a)):
	if a[i] > a[i - 1]:
		print(len(a) - i)
		break
else:
	print(0)


def main():
	n = int(input())
	aa = list(map(int, input().split()))
	m = aa[-1]
	for i in range(n - 2, -2, -1):
		a = aa[i]
		if m < a:
			break
		m = a
	print(i + 1)
main()


(n, ar) = (int(input()), [int(x) for x in input().split()][::-1])
ans = 0
for i in range(1, n):
	if ar[i] > ar[i - 1]:
		ans = n - i
		break
print(ans)


n = int(input())
s = input().split()
a = 0
b = 0
for i in range(n - 1):
	if int(s[i]) < int(s[i + 1]):
		a = a + 1
	else:
		b = b + 1 + a
		a = 0
print(b)


n = int(input())
arr = list(map(int, input().split()))
(temp, count) = (1000000, 0)
for i in reversed(arr):
	if i < temp:
		temp = i
		count += 1
	if i > temp:
		break
print(n - count)


n = int(input())
l = [int(x) for x in input().split()]
l.reverse()
for i in range(1, n):
	if l[i] > l[i - 1]:
		print(n - i)
		exit(0)
print(0)


import sys
import itertools as it
import math as mt
import collections as cc
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
i = n - 1
while i > 0 and l[i] > l[i - 1]:
	i -= 1
print(i)


n = int(input())
l = list(map(int, input().split()))
ans = -1
for i in range(n - 1):
	if l[i] > l[i + 1]:
		ans = i
print(ans + 1)


import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n,) = I()
a = I()
i = n - 1
while i > 0 and a[i - 1] < a[i]:
	i -= 1
print(i)


input()
t = [int(x) for x in input().split()]
m = [True] + [t[i] > t[i + 1] for i in range(len(t) - 1)]
print(len(m) - 1 - list(reversed(m)).index(True))


n = int(input())
a = list(map(int, input().split()))
i = n - 1
while i and a[i] > a[i - 1]:
	i = i - 1
print(i)


n = int(input())
a = list(map(int, input().split()))[::-1]
c = 0
for i in range(1, n):
	if a[i] > a[i - 1]:
		c = n - i
		break
print(c)


n = int(input())
temp = 0
c = 0
a = input().split()
for i in range(0, n):
	if temp - int(a[i]) > 0:
		c = i + 1
	temp = int(a[i])
if c != 0:
	print(c - 1)
else:
	print(0)


def ordem_crescente(lista, n, i, crescente):
	while i < n - 1:
		if int(lista[i]) > int(lista[i + 1]):
			crescente[0] = i - 1
			return False
		i += 1
	return True
n = int(input())
fim = input().split(' ')
count = 0
i = 0
crescente = [-1]
while i < n:
	if i >= crescente[0]:
		num = int(fim[i])
		if i + 1 < num:
			count += 1
		elif i + 1 == num:
			if not ordem_crescente(fim, n, i, crescente):
				count += 1
			else:
				break
		elif not ordem_crescente(fim, n, i, crescente):
			count += 1
		else:
			break
	else:
		count += 1
	i += 1
print(count)


n = int(input())
t = list(map(int, input().split()))
i = n - 1
while t[i] > t[i - 1]:
	i = i - 1
print(i)


n = int(input())
arr = list(map(int, input().split()))
i = n - 1
while arr[i] > arr[i - 1]:
	i -= 1
print(i)


n = int(input())
a = str(input()).split(' ')
ma = 0
output = 0
for i in range(n - 1):
	if int(a[i]) < int(a[i + 1]):
		ma += 1
	else:
		output += 1 + ma
		ma = 0
print(output)


n = input()
arr = input().split(' ')
asc = 1
x = int(arr[0])
for i in range(1, int(n)):
	if int(arr[i]) > x:
		asc += 1
	else:
		asc = 1
	x = int(arr[i])
print(int(n) - asc)


n = int(input())
t = [int(i) for i in input().split()]
last_new = -1
for i in range(len(t)):
	if i == len(t) - 1:
		break
	if t[i] > t[i + 1]:
		last_new = i
print(last_new + 1)


n = int(input())
old_pos = list(map(int, input().split()))
real_pos = list(reversed(old_pos))
flag = True
for i in range(1, n):
	if real_pos[i] > real_pos[i - 1]:
		print(n - i)
		flag = False
		break
if flag == True:
	print(0)


n = int(input())
lista = input().split()
cont = 0
i = n - 1
if n == 1:
	print('0')
else:
	while i > 0:
		if int(lista[i]) > int(lista[i - 1]):
			cont += 1
			i -= 1
			if i == 0:
				cont += 1
		else:
			cont += 1
			break
	print(n - cont)


n = int(input())
a = list(map(int, input().split()))
no = n - 1
minm = a[-1]
for i in range(n - 2, -1, -1):
	if a[i] <= minm:
		no -= 1
		minm = a[i]
	else:
		break
print(no)


n = int(input())
inStr = input()
pos = [int(x) for x in inStr.split()]
min = n
ans = 0
for i in range(n - 1, -1, -1):
	if pos[i] > min:
		ans = i + 1
		break
	elif pos[i] < min:
		min = pos[i]
print(ans)


n = int(input())
aux = input().split()
first = int(aux[0])
flag = 1
for i in range(1, n):
	if int(aux[i]) < first:
		flag = 1
	else:
		flag += 1
	first = int(aux[i])
print(n - flag)


n = int(input())
threads = list(map(int, input().split()))
count = 0
for i in range(n - 1):
	if threads[i] > threads[i + 1]:
		count = i + 1
print(count)


from sys import stdin
inp = stdin.readline
n = int(inp())
a = list(map(int, inp().split()))
ans = 0
cur_max = a[0]
for i in range(n - 1, 0, -1):
	if a[i] < a[i - 1]:
		print(i)
		exit()
print(0)


import sys
n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))[::-1]
ans = 0
acc = n
pre = 9999999999999
for i in range(n):
	if l[i] < pre:
		ans += 1
		pre = l[i]
	else:
		break
print(n - ans)


n = int(input())
q = list(map(int, input().split()))
index = 0
for i in range(n - 1, 0, -1):
	if q[i - 1] > q[i]:
		index = i
		break
print(index)


def main():
	n = int(input())
	threads = [int(i) for i in input().split()]
	i = len(threads) - 1
	while i > 0:
		if threads[i] < threads[i - 1]:
			print(i)
			return
		i -= 1
	print(0)
main()


n = int(input())
l = list(map(int, input().split()))
x = 0
for i in range(n - 1, -1, -1):
	if l[i] < l[i - 1]:
		x = i
		break
print(x)


nr_threads = int(input())
old_position = list(map(int, input().split()))
ans = nr_threads - 1
if nr_threads == 1:
	print(0)
	quit()
i = ans
while i > 0:
	if old_position[i - 1] > old_position[i]:
		print(ans)
		quit()
	else:
		i -= 1
		ans -= 1
print(ans)


t = int(input())
arr = list(map(int, input().split()))
i = t - 1
while i > 0 and arr[i] > arr[i - 1]:
	i -= 1
print(i)


n = int(input())
arr = list(map(int, input().split()))
ans = n - 1
for i in range(-1, -n, -1):
	if arr[i] > arr[i - 1]:
		ans -= 1
	else:
		break
print(ans)


noth = int(input())
oldpos = [int(num) for num in input().split()]
newpos = [i + 1 for i in range(noth)]
counter = 0
if oldpos != newpos:
	for i in reversed(range(1, noth)):
		if oldpos[i - 1] > oldpos[i]:
			counter = i
			break
print(counter)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(n - 2, -1, -1):
	if a[i + 1] < a[i]:
		print(i + 1)
		break
else:
	print(0)


n = int(input())
x = [int(i) for i in input().split(' ')]
i = n - 1
while i > 0:
	if x[i] < x[i - 1]:
		break
	i -= 1
print(i)


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

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')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
n = ii()
arr = rr()
c = 0
i = n - 1
while arr[i] > arr[i - 1]:
	i -= 1
print(i)


n = int(input())
t = input().split()
thread = []
for i in range(n):
	thread.append(int(t[i]))
position = 0
for j in range(n - 1):
	if thread[j] > thread[j + 1]:
		position = j + 1
print(position)


n = int(input())
l = [int(i) for i in input().split()]
ans = 0
f = 0
for i in range(n - 1, 0, -1):
	if l[i] < l[i - 1]:
		print(i)
		f = 1
		break
if not f:
	print(f)


n = int(input())
pos = list(map(int, input().split()))
last = -1
for i in range(n - 1):
	if pos[i] > pos[i + 1]:
		last = i
print(last + 1)


num = int(input())
arr = list(map(int, input().split()))
i = num - 1
while arr[i] > arr[i - 1]:
	i -= 1
print(i)


n = int(input())
a = [int(x) for x in input().split()]
answer = 0
last = a[-1]
for v in reversed(a):
	if v > last:
		break
	answer += 1
	last = v
print(len(a) - answer)


N = int(input())
X = list(map(int, input().split()))
Index = N - 1
for i in range(N - 1, 0, -1):
	if X[i] < X[i - 1]:
		print(i)
		exit()
print(0)


import sys
input = sys.stdin.readline
from collections import deque, defaultdict
from math import log10, ceil, factorial as F
I = lambda : int(input())
L = lambda : list(map(int, input().split()))
T = lambda : map(int, input().split())
n = I()
lis = L()
i = n - 1
while i > 0 and lis[i - 1] < lis[i]:
	i -= 1
print(i)


n = int(input())
threads = [int(i) for i in input().split()]
min = threads[n - 1]
new = 0
for i in range(2, n + 1):
	if threads[n - i] > min:
		new = n - i + 1
		break
	else:
		min = threads[n - i]
print(new)


import re, sys, string, operator, functools, fractions, collections
from random import *
sys.setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
RI = lambda : list(map(int, input().split()))
RS = lambda : input().rstrip().split()
mod = 1000000000.0 + 7
eps = 1e-06
n = RI()[0]
a = RI()
ans = 1
for i in range(n - 1, 0, -1):
	if a[i - 1] > a[i]:
		break
	ans += 1
print(n - ans)


R = input
I = lambda : map(int, R().split())
n = int(R())
a = list(I())[::-1] + [999999]
for i in range(n):
	if a[i + 1] > a[i]:
		print(n - i - 1)
		break


n = int(input(''))
a = [int(x) for x in input('').split(' ')]
output = 0
cache = 0
for x in range(n - 1):
	if a[x] > a[x + 1]:
		output += 1 + cache
		cache = 0
	else:
		cache += 1
print(output)