One day Polycarp decided to rewatch his absolute favourite episode of well-known TV series "Tufurama". He was pretty surprised when he got results only for season 7 episode 3 with his search query of "Watch Tufurama season 3 episode 7 online full hd free". This got Polycarp confused — what if he decides to rewatch the entire series someday and won't be able to find the right episodes to watch? Polycarp now wants to count the number of times he will be forced to search for an episode using some different method.

TV series have n seasons (numbered 1 through n), the i-th season has a_{i} episodes (numbered 1 through a_{i}). Polycarp thinks that if for some pair of integers x and y (x < y) exist both season x episode y and season y episode x then one of these search queries will include the wrong results. Help Polycarp to calculate the number of such pairs!


-----Input-----

The first line contains one integer n (1  ≤ n  ≤  2·10^5) — the number of seasons.

The second line contains n integers separated by space a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — number of episodes in each season.


-----Output-----

Print one integer — the number of pairs x and y (x < y) such that there exist both season x episode y and season y episode x.


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

Output
0

Input
3
8 12 7

Output
3

Input
3
3 2 1

Output
2



-----Note-----

Possible pairs in the second example:  x = 1, y = 2 (season 1 episode 2 [Image] season 2 episode 1);  x = 2, y = 3 (season 2 episode 3 [Image] season 3 episode 2);  x = 1, y = 3 (season 1 episode 3 [Image] season 3 episode 1). 

In the third example:  x = 1, y = 2 (season 1 episode 2 [Image] season 2 episode 1);  x = 1, y = 3 (season 1 episode 3 [Image] season 3 episode 1).

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import bisect

def lowbit(x):
	return x & -x

def add(i, x):
	while i <= n:
		bit[i].append(x)
		i += lowbit(i)

def query(i, x):
	s = 0
	while i > 0:
		pos = bisect.bisect_left(bit[i], x)
		s += len(bit[i]) - pos
		i -= lowbit(i)
	return s
n = int(input())
bit = [[] for i in range(n + 2)]
a = [int(i) for i in input().split()]
a.insert(0, 0)
for i in range(1, n + 1):
	add(i, a[i])
ans = 0
for i in range(1, n + 1):
	bit[i].sort()
for i in range(1, n + 1):
	if a[i] <= i:
		continue
	ans += query(min(n, a[i]), i) - query(i, i)
print(ans)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

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

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
N = int(input())
A = li()
Seg = SegmentTree([0] * N, lambda x, y: x + y, 0)
query = []
for i in range(N):
	query.append((i + 1, -1))
	query.append((A[i], i))
query.sort()
res = 0
for (val, t) in query[::-1]:
	if t == -1:
		idx = val - 1
		a = A[idx]
		res += Seg.query(idx + 1, min(a, N))
	else:
		idx = t
		Seg.update(t, 1)
print(res)


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 Counter
import math
from string import ascii_lowercase as al
import bisect

def add(i, val):
	while i <= n:
		bit[i].append(val)
		i += i & -i

def query(i, x):
	s = 0
	while i > 0:
		pos = bisect.bisect_left(bit[i], x)
		s += len(bit[i]) - pos
		i -= i & -i
	return s
n = int(input())
bit = [[] for i in range(n + 3)]
a = [int(i) for i in input().split()]
a.insert(0, 0)
for i in range(1, n + 1):
	add(i, a[i])
for i in range(1, n + 1):
	bit[i].sort()
ans = 0
for i in range(1, n + 1):
	if a[i] <= i:
		continue
	ans += query(min(a[i], n), i) - query(i, i)
print(ans)


import sys
from collections import defaultdict

class BIT_RSQ(object):
	__slots__ = ['nodes', 'size']

	def __init__(self, size: int):
		self.nodes = [0] * (size + 1)
		self.size = size + 1

	def add(self, index: int, value: int):
		while index < self.size:
			self.nodes[index] += value
			index += index & -index

	def sum(self, right: int):
		result = 0
		while right:
			result += self.nodes[right]
			right -= right & -right
		return result
n = int(input())
a = list(map(int, input().split()))
bit = BIT_RSQ(n + 10)
remove = defaultdict(list)
ans = 0
for (i, x) in enumerate(a, start=1):
	ans += bit.sum(min(i, x))
	if i < x:
		bit.add(i, 1)
		remove[min(n + 1, x)].append(i)
	for j in remove[i]:
		bit.add(j, -1)
print(ans)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(input())
a = list(rrd())
bit = [0] * (n + 100)

def ins(x):
	while x <= n:
		bit[x] += 1
		x += x & -x

def get(l):
	tot = 0
	while l:
		tot += bit[l]
		l -= l & -l
	return tot
ta = []
pans = 0
for i in range(len(a)):
	if a[i] > i:
		pans += 1
	ta.append([i + 1, a[i]])
ta.sort(key=lambda x: x[1])
ans = 0
now = 0
for x in ta:
	while now < min(n, x[1]):
		if a[now] <= n:
			ins(a[now])
		now += 1
	ans += now - get(x[0] - 1)
print((ans - pans) // 2)


import sys

class RangeBit:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.dataAdd = [0 for _ in range(sz)]
		self.dataMul = [0 for _ in range(sz)]

	def sum(self, i):
		assert i > 0
		(add, mul, start) = (0, 0, i)
		while i > 0:
			add += self.dataAdd[i]
			mul += self.dataMul[i]
			i -= i & -i
		return mul * start + add

	def add(self, left, right, by):
		assert 0 < left <= right
		self._add(left, by, -by * (left - 1))
		self._add(right, -by, by * right)

	def _add(self, i, mul, add):
		assert i > 0
		while i < self.size:
			self.dataAdd[i] += add
			self.dataMul[i] += mul
			i += i & -i
n = int(input())
l = list(map(int, sys.stdin.readline().split()))
queries = []
for i in range(n):
	if min(l[i], n) >= i + 2:
		queries.append((i + 2, min(l[i], n), i + 1))
result = 0
a = sorted(list(zip(list(range(1, n + 1)), l)) + queries, key=lambda x: (-x[-1], len(x)))
ft = RangeBit(n + 1)
for el in a:
	if len(el) == 2:
		(ind, val) = el
		ft.add(ind, ind, 1)
	else:
		(fr, to, val) = el
		result += ft.sum(to) - (ft.sum(fr - 1) if fr > 1 else 0)
print(result)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(rd())
a = list(rrd())
bit = [0] * (n + 10)

def get(x):
	tot = 0
	while x:
		tot += bit[x]
		x -= x & -x
	return tot

def ins(x):
	while x <= n + 1:
		bit[x] += 1
		x += x & -x
b = []
preans = 0
for (i, v) in enumerate(a):
	if v > i:
		preans += 1
	b.append([i + 1, v])
b.sort(key=lambda x: x[1])
ans = 0
i = 0
for x in b:
	while i < n and i < x[1]:
		ins(a[i])
		i += 1
	ans += i - get(x[0] - 1)
print((ans - preans) // 2)


from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
ans = 0

class fenwick:

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

	def to_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j):
		return self.to_sum(j) - self.to_sum(i - 1)
Q = fenwick(n + 10)
BIGGER = n + 5
seq = [(a[i], i) for i in range(n)]
A = a.copy()
for i in range(n):
	if i < a[i]:
		ans -= 1
a.sort()
seq.sort(key=lambda x: x[0])
lindex = 0
for (a_r, r) in seq:
	if a_r > n:
		ans += n - bisect_right(a, r)
		continue
	else:
		for i in range(lindex, a_r):
			if A[i] <= n:
				Q.add(A[i], 1)
			else:
				Q.add(BIGGER, 1)
		ans += Q.get(r + 1, BIGGER + 1)
		lindex = a_r
ans //= 2
print(ans)


import types
_atcoder_code = '\n# Python port of AtCoder Library.\n__all__ = ["string","lazysegtree","convolution","maxflow","modint"\n    ,"mincostflow","segtree","_scc","_math","math","dsu","twosat","fenwicktree","scc","_bit","lca","unverified","graph","matrix","algebra","combinatorics"]\n__version__ = \'0.0.1\'\n'
atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)
_atcoder__bit_code = '\ndef _ceil_pow2(n: int) -> int:\n    x = 0\n    while (1 << x) < n:\n        x += 1\n\n    return x\n\n\ndef _bsf(n: int) -> int:\n    x = 0\n    while n % 2 == 0:\n        x += 1\n        n //= 2\n\n    return x\n'
atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)
_atcoder_segtree_code = "\nimport typing\n\n# import atcoder._bit\n\n\nclass SegTree:\n \n    '''\n    Segment Tree Library.\n    op(S,S) -> S\n    e = Identity element\n    \n    SegTree(op,e,n) := Initialized by [e]*(n)\n    SegTree(op,e,vector) := Initialized by vector\n    '''\n\n    def __init__(self,\n                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],\n                 e: typing.Any,\n                 v: typing.Union[int, typing.List[typing.Any]]) -> None:\n        self._op = op\n        self._e = e\n\n        if isinstance(v, int):\n            v = [e] * v\n\n        self._n = len(v)\n        self._log = atcoder._bit._ceil_pow2(self._n)\n        self._size = 1 << self._log\n        self._d = [e] * (2 * self._size)\n\n        for i in range(self._n):\n            self._d[self._size + i] = v[i]\n        for i in range(self._size - 1, 0, -1):\n            self._update(i)\n\n    def set(self, p: int, x: typing.Any) -> None:\n        '''\n        a[p] -> x in O(logN).\n        '''\n        assert 0 <= p < self._n\n\n        p += self._size\n        self._d[p] = x\n        for i in range(1, self._log + 1):\n            self._update(p >> i)\n\n    def increment(self, p: int, x : typing.Any) -> None:\n        '''\n        a[p] -> a[p] + x in O(logN).\n        '''\n        assert 0 <= p < self._n\n\n        p += self._size\n        self._d[p] += x\n        for i in range(1,self._log + 1):\n            self._update(p >> i)\n        \n    def get(self, p: int) -> typing.Any:\n        '''\n        return a[p] in O(1).\n        '''\n        assert 0 <= p < self._n\n\n        return self._d[p + self._size]\n\n    def prod(self, left: int, right: int) -> typing.Any:\n        '''\n        return op(a[l...r)) in O(logN).\n        '''\n        assert 0 <= left <= right <= self._n\n        sml = self._e\n        smr = self._e\n        left += self._size\n        right += self._size\n\n        while left < right:\n            if left & 1:\n                sml = self._op(sml, self._d[left])\n                left += 1\n            if right & 1:\n                right -= 1\n                smr = self._op(self._d[right], smr)\n            left >>= 1\n            right >>= 1\n\n        return self._op(sml, smr)\n\n    def all_prod(self) -> typing.Any:\n        return self._d[1]\n\n    def max_right(self, left: int,\n                  f: typing.Callable[[typing.Any], bool]) -> int:\n        '''\n        let f(S) -> bool and l is const.\n        return maximum r for which f(op[l...r)) == true is satisfied, in O(logN).\n        '''\n        assert 0 <= left <= self._n\n        # assert f(self._e)\n\n        if left == self._n:\n            return self._n\n\n        left += self._size\n        sm = self._e\n\n        first = True\n        while first or (left & -left) != left:\n            first = False\n            while left % 2 == 0:\n                left >>= 1\n            if not f(self._op(sm, self._d[left])):\n                while left < self._size:\n                    left *= 2\n                    if f(self._op(sm, self._d[left])):\n                        sm = self._op(sm, self._d[left])\n                        left += 1\n                return left - self._size\n            sm = self._op(sm, self._d[left])\n            left += 1\n\n        return self._n\n\n    def min_left(self, right: int,\n                 f: typing.Callable[[typing.Any], bool]) -> int:\n        '''\n        let f(S) -> bool and r is const.\n        return minimum l for which f(op[l...r)) == true is satisfied, in O(logN).\n        '''\n\n        assert 0 <= right <= self._n\n        # assert f(self._e)\n\n        if right == 0:\n            return 0\n\n        right += self._size\n        sm = self._e\n\n        first = True\n        while first or (right & -right) != right:\n            first = False\n            right -= 1\n            while right > 1 and right % 2:\n                right >>= 1\n            if not f(self._op(self._d[right], sm)):\n                while right < self._size:\n                    right = 2 * right + 1\n                    if f(self._op(self._d[right], sm)):\n                        sm = self._op(self._d[right], sm)\n                        right -= 1\n                return right + 1 - self._size\n            sm = self._op(self._d[right], sm)\n\n        return 0\n\n    def _update(self, k: int) -> None:\n        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])\n"
atcoder.segtree = types.ModuleType('atcoder.segtree')
atcoder.segtree.__dict__['atcoder'] = atcoder
atcoder.segtree.__dict__['atcoder._bit'] = atcoder._bit
exec(_atcoder_segtree_code, atcoder.segtree.__dict__)
SegTree = atcoder.segtree.SegTree
import sys

def input():
	return sys.stdin.readline().rstrip()
from collections import deque

def main():
	n = int(input())
	a = list(map(int, input().split()))
	Q = SegTree(lambda x, y: x + y, 0, [1] * n)
	b = [(a[i], i) for i in range(n)]
	b.sort(key=lambda x: x[0])
	b = deque(b)
	ans = 0
	for i in range(n):
		while b and b[0][0] < i + 1:
			(val, idx) = b.popleft()
			Q.set(idx, 0)
		if min(a[i], n) > 0:
			ans += Q.prod(0, min(a[i], n))
	for i in range(n):
		if a[i] >= i + 1:
			ans -= 1
	assert ans % 2 == 0
	ans //= 2
	print(ans)
	return 0
main()