Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person. 
Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A.  Also, people will not friend request themselves.
How many total friend requests are made?
Example 1:
Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:
Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.
Example 3:
Input: [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

 
Notes:

1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

Starter code: class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        

Solutions:
class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = [0] * 121
		s = [0] * 121
		for a in ages:
			count[a] += 1
		for i in range(1, 121):
			s[i] = s[i - 1] + count[i]
		res = 0
		for i in range(15, 121):
			edge = i // 2 + 7
			num = s[i] - s[edge]
			res += count[i] * num - count[i]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def wantToRequest(A, B):
			return not (B <= 0.5 * A + 7 or B > A)
		count = Counter(ages)
		ans = 0
		ages = [*sorted(count.keys())]
		for (i, a) in enumerate(ages):
			for j in range(0, i + 1):
				b = ages[j]
				if wantToRequest(a, b):
					ans += count[a] * count[b] if a != b else count[a] * (count[b] - 1)
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		sum = 0
		counts = collections.Counter(ages)
		ages = sorted(counts.keys())
		for A in range(0, len(ages)):
			for B in range(0, len(ages)):
				condition1 = ages[B] <= 0.5 * ages[A] + 7
				condition2 = ages[B] > ages[A]
				condition3 = ages[B] > 100 and ages[A] < 100
				if not (condition1 or condition2 or condition3):
					if A != B:
						sum += counts[ages[A]] * counts[ages[B]]
					else:
						sum += (counts[ages[A]] - 1) * counts[ages[B]]
		return sum


class Solution(object):

	def numFriendRequests(self, ages):
		count = [0] * 121
		for age in ages:
			count[age] += 1
		ans = 0
		for (ageA, countA) in enumerate(count):
			for (ageB, countB) in enumerate(count):
				if ageA * 0.5 + 7 >= ageB:
					continue
				if ageA < ageB:
					continue
				if ageA < 100 < ageB:
					continue
				ans += countA * countB
				if ageA == ageB:
					ans -= countA
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = [0 for _ in range(121)]
		for a in ages:
			count[a] += 1
		ans = 0
		for (a, cnt_a) in enumerate(count):
			for (b, cnt_b) in enumerate(count):
				if a <= 0.5 * b + 7:
					continue
				if a > b:
					continue
				if a > 100 and b < 100:
					continue
				ans += cnt_a * cnt_b
				if a == b:
					ans -= cnt_a
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def request(a, b):
			return not (b <= 0.5 * a + 7 or b > a or (b > 100 and a < 100))
		c = collections.Counter(ages)
		return sum((request(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c))


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		if not ages:
			return 0
		freq = Counter(ages)

		def can_request(a, b):
			return not (b <= 0.5 * a + 7 or b > a or (b > 100 and a < 100))
		ans = 0
		for a1 in range(1, 121):
			for a2 in range(1, 121):
				if can_request(a1, a2):
					ans += freq[a1] * freq[a2] if a1 != a2 else freq[a1] * (freq[a1] - 1)
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		if not ages or len(ages) < 2:
			return 0
		res = 0
		d = [0] * 121
		for age in ages:
			d[age] += 1
		for A in range(121):
			for B in range(121):
				count = 0
				if B <= A and B > A // 2 + 7:
					count += d[A] * d[B]
				if A == B and count:
					count -= d[A]
				res += count
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def invert(a):
			return -1 * a
		ages.sort(key=invert)
		age_request_map = collections.defaultdict(int)
		num_requests = 0
		for age in ages:
			if age <= 14:
				break
			num_requests += age_request_map[age]
			age_request_map[age] += 1
			lowest_age = floor(age * 0.5 + 7) + 1
			for i in range(lowest_age, age + 1):
				age_request_map[i] += 1
		return num_requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_dic = {age: ages.count(age) for age in range(1, 121)}
		pairs = 0
		for A in range(1, 121):
			for B in range(1, 121):
				if B <= 0.5 * A + 7:
					continue
				elif B > A:
					continue
				elif B > 100 and A < 100:
					continue
				else:
					pairs += age_dic[A] * age_dic[B]
					if A == B:
						pairs -= age_dic[A]
		return pairs


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_cnt = [0] * 121
		for age in ages:
			age_cnt[age] += 1
		res = 0
		for (ageA, cntA) in enumerate(age_cnt):
			for (ageB, cntB) in enumerate(age_cnt):
				if ageB <= 0.5 * ageA + 7 or ageB > ageA or (ageB > 100 and ageA < 100):
					continue
				res += cntA * cntB
				if ageA == ageB:
					res -= cntA
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		counter = Counter(ages)
		ages = list(counter.keys())
		res = 0
		for a in ages:
			for b in ages:
				if b <= 0.5 * a + 7:
					continue
				if b > a:
					continue
				if b > 100 and a < 100:
					continue
				if a == b:
					res += counter[a] * (counter[a] - 1)
				else:
					res += counter[a] * counter[b]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages = sorted(ages)
		res = 0
		prev = None
		for i in range(len(ages) - 1, -1, -1):
			if i == len(ages) - 1 or ages[i] != ages[i + 1]:
				prev = i
			(low, right) = (0, prev - 1)
			while low < right:
				mid = (low + right) // 2
				if ages[mid] <= 0.5 * ages[i] + 7:
					low = mid + 1
				else:
					right = mid
			if ages[low] > 0.5 * ages[prev] + 7:
				res += prev - low
		return res


from collections import Counter

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def is_valid(a, b):
			return not any([b <= 0.5 * a + 7, b > a, b > 100 and a < 100])
		counts = Counter(ages)
		ages = list(counts)
		requests = 0
		for i in range(len(ages)):
			for j in range(len(ages)):
				count = counts[ages[i]] * (counts[ages[i]] - 1) if i == j else counts[ages[i]] * counts[ages[j]]
				requests += int(is_valid(ages[i], ages[j])) * count
		return requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		cnt = collections.Counter(ages)
		ans = 0
		for age in ages:
			cnt[age] -= 1
			(left, right) = (age // 2 + 8, age)
			ans += sum((cnt[age] for age in range(left, right + 1)))
			cnt[age] += 1
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def req(A, B):
			if B <= 0.5 * A + 7 or B > A or (B > 100 and A < 100):
				return False
			return True
		cnt = Counter(ages)
		ans = 0
		for i in cnt:
			if cnt[i] > 1 and req(i, i):
				ans += cnt[i] * (cnt[i] - 1)
			for j in cnt:
				if i != j and req(i, j):
					ans += cnt[i] * cnt[j]
		return ans


from collections import Counter
import math

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		counter = Counter(ages)
		count = 0
		for age_A in ages:
			max_age = age_A
			min_age = 0.5 * age_A + 7
			for age_B in range(math.floor(min_age) + 1, max_age + 1):
				count += counter[age_B]
				if age_B == age_A:
					count -= 1
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages = sorted(ages)
		(count, temp_count) = (0, 0)
		for i in range(len(ages) - 1, -1, -1):
			if i + 1 < len(ages) and ages[i + 1] == ages[i]:
				count += temp_count
				continue
			(temp_count, current) = (0, i - 1)
			age = 0.5 * ages[i] + 7
			while current >= 0 and ages[current] > age:
				temp_count += 1
				current = current - 1
			count = count + temp_count
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()
		res = 0
		i = 0
		while i < len(ages):
			if ages[i] <= 14:
				i += 1
			else:
				break
		if i == len(ages):
			return 0
		leftmost = i
		for i in range(leftmost, len(ages)):
			(left, right) = (leftmost, i - 1)
			edge = ages[i] * 0.5 + 7
			while left <= right:
				m = (left + right) // 2
				if ages[m] <= edge:
					left = m + 1
				else:
					right = m - 1
			res += i - left
			(left, right) = (i + 1, len(ages) - 1)
			while left <= right:
				m = (left + right) // 2
				if ages[m] <= ages[i]:
					left = m + 1
				else:
					right = m - 1
			left -= 1
			res += left - i
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ageIdx = defaultdict(list)
		for (i, age) in enumerate(ages):
			ageIdx[age].append(i)
		count = 0
		for age in ageIdx:
			lowerBound = int(1 / 2 * age) + 7 + 1
			upperBound = age
			for A in ageIdx[age]:
				for candAge in range(lowerBound, upperBound + 1):
					if candAge in ageIdx:
						if candAge != age:
							count += len(ageIdx[candAge])
						else:
							count += len(ageIdx[candAge]) - 1
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_range = [0] * 121
		ages = sorted(ages)
		ans = 0
		for age in ages:
			for i in range(age - 1, -1, -1):
				if i <= 0.5 * age + 7:
					break
				ans += age_range[i]
			if age > 0.5 * age + 7:
				ans += age_range[age] * 2
			age_range[age] += 1
		return ans


class Solution:

	def firstLTE(self, lowerBound, ages, endIndex):
		if endIndex < 0:
			return 0
		l = 0
		r = endIndex
		while l < r:
			m = (l + r) // 2
			if ages[m] <= lowerBound:
				l = m + 1
			else:
				r = m
		if l <= r and ages[l] > lowerBound:
			return l
		return endIndex + 1

	def findEarliest(self, key, ages, endIndex):
		if endIndex < 0:
			return -1
		l = 0
		r = endIndex
		while l < r:
			m = (l + r) // 2
			if ages[m] >= key:
				r = m
			else:
				l = m + 1
		if l <= endIndex and ages[l] == key:
			return l
		return -1

	def numFriendRequests(self, ages: List[int]) -> int:
		if not ages:
			return 0
		numRequests = 0
		ages.sort()
		for (i, a) in enumerate(ages):
			lowerBound = a * 0.5 + 7
			startIndex = self.firstLTE(lowerBound, ages, i - 1)
			numRequests += i - startIndex
			if a > lowerBound:
				startIndex = self.findEarliest(a, ages, i - 1)
				if startIndex >= 0 and startIndex < i:
					numRequests += i - startIndex
		return numRequests


import collections

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_count = collections.Counter(ages)
		res = 0
		for (age_A, count_A) in age_count.items():
			for (age_B, count_B) in age_count.items():
				if not age_B <= age_A * 0.5 + 7 and (not age_B > age_A):
					if age_A == age_B:
						res += count_A * (count_A - 1)
					else:
						res += count_A * count_B
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages = sorted(ages)
		print(ages)

		def bound(a):
			low = a // 2 + 8
			hi = a
			return (min(low, a), hi)

		def getlow(v):
			(lo, hi) = (0, len(ages))
			while lo < hi:
				mid = (lo + hi) // 2
				if ages[mid] >= v:
					hi = mid
				else:
					lo = mid + 1
			return hi

		def getupper(v):
			(lo, hi) = (0, len(ages))
			while lo < hi:
				mid = (lo + hi) // 2
				if ages[mid] <= v:
					lo = mid + 1
				else:
					hi = mid
			return hi - 1
		count = 0
		for i in range(len(ages)):
			if ages[i] <= 14:
				continue
			(minv, maxv) = bound(ages[i])
			c = getupper(maxv) - getlow(minv)
			count += c
		p = 115
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages = sorted(ages, reverse=True)
		n = len(ages)
		dp = [0] * n
		res = 0
		for i in range(n):
			if i > 0 and ages[i] == ages[i - 1]:
				dp[i] = dp[i - 1]
				res += dp[i]
				continue
			for j in range(i + 1, n):
				if ages[j] <= 0.5 * ages[i] + 7:
					break
				else:
					dp[i] += 1
			res += dp[i]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		if ages == []:
			return 0
		ages.sort()
		res = 0
		for i in range(len(ages) - 1, -1, -1):
			if ages[i] < 15:
				break
			age = ages[i]
			left = self.binary_search_left(ages, 0, i, age // 2 + 8)
			right = self.binary_search_right(ages, i, len(ages) - 1, age)
			res += max(0, right - left)
		return res

	def binary_search_left(self, ages, start, end, target):
		while start + 1 < end:
			mid = (start + end) // 2
			if ages[mid] < target:
				start = mid
			else:
				end = mid
		if ages[start] >= target:
			return start
		if ages[end] >= target:
			return end
		return -1

	def binary_search_right(self, ages, start, end, target):
		while start + 1 < end:
			mid = (start + end) // 2
			if ages[mid] <= target:
				start = mid
			else:
				end = mid
		if ages[end] <= target:
			return end
		if ages[start] <= target:
			return start
		return -1


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()

		def count(a):
			(i, j) = (0, len(ages) - 1)
			while i < j:
				k = (i + j + 1) // 2
				if ages[k] <= a:
					i = k
				else:
					j = k - 1
			u = i
			v = a // 2 + 7
			(i, j) = (0, len(ages) - 1)
			while i < j:
				k = (i + j) // 2
				if ages[k] <= v:
					i = k + 1
				else:
					j = k
			l = i
			return u - l if l <= u else 0
		return sum((count(a) for a in ages))


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = 0
		ages.sort()
		for (i, age) in enumerate(ages):
			minTarget = age // 2 + 7
			maxTarget = age
			minIdx = self.binFinder(ages, minTarget)
			maxIdx = self.binFinder(ages, maxTarget)
			count += max(0, maxIdx - minIdx - 1)
		return count

	def binFinder(self, arr, target):
		(left, right) = (0, len(arr) - 1)
		while left <= right:
			mid = left + (right - left) // 2
			if arr[mid] <= target:
				left = mid + 1
			else:
				right = mid - 1
		return left


def count_smaller_than(ages, target):
	left = 0
	right = len(ages) - 1
	while left <= right:
		mid = left + (right - left) // 2
		if ages[mid] < target:
			left = mid + 1
		else:
			right = mid - 1
	return left
import math

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()
		friend_requests = 0
		for i in range(len(ages)):
			age_a = ages[i]
			smaller_than = count_smaller_than(ages, math.floor(0.5 * age_a) + 8)
			smaller_than_i = count_smaller_than(ages, age_a + 1)
			a_requests = max(0, smaller_than_i - 1 - smaller_than)
			friend_requests += a_requests
		return friend_requests


class Solution:

	def B_search(self, nums, target):
		(low, high) = (0, len(nums) - 1)
		while low < high:
			mid = low + (high - low) // 2
			if nums[mid] < target:
				low = mid + 1
			else:
				high = mid
		return high

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()
		count = 0
		for age in ages:
			left = self.B_search(ages, int(0.5 * age + 7) + 1)
			right = self.B_search(ages, age + 1)
			if right == len(ages) - 1 and ages[right] == age:
				right += 1
			if ages[left] == 0.5 * age + 7:
				left += 1
			count += max(0, right - left - 1)
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()
		ans = 0
		(l, r, N) = (0, 0, len(ages))
		same_count = 0
		while r < N:
			same_count = 1
			while r + 1 < N and ages[r + 1] == ages[r]:
				same_count += 1
				r += 1
			while l < r and ages[l] <= 0.5 * ages[r] + 7:
				l += 1
			if l != r:
				ans += same_count * (r - l)
			r += 1
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		n = len(ages)
		if n < 2:
			return 0
		ages.sort()
		mins = [0] * n
		pairs = [0] * n
		mins[0] = ages[0] / 2 + 7
		for i in range(1, n):
			mins[i] = (ages[i] - ages[i - 1]) / 2 + mins[i - 1]
			if ages[i - 1] <= mins[i]:
				continue
			if mins[i] == mins[i - 1]:
				pairs[i] = pairs[i - 1] + 2
				continue
			j = i - 1
			while j >= 0 and ages[j] > mins[i]:
				pairs[i] += 1
				if ages[j] == ages[i]:
					pairs[i] += 1
				j -= 1
		return sum(pairs)


from collections import Counter

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		dic = Counter(ages)
		res = 0
		for (ageA, cntA) in list(dic.items()):
			for (ageB, cntB) in list(dic.items()):
				if ageB <= 0.5 * ageA + 7 or ageB > ageA or (ageB > 100 and ageA < 100):
					continue
				res += cntA * cntB
				if ageA == ageB:
					res -= cntA
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def friendRequests(age_a, age_b):
			if age_b <= 0.5 * age_a + 7 or age_b > age_a:
				return False
			return True
		age_groups = collections.Counter(ages)
		total_requests = 0
		for (age_a, count_a) in list(age_groups.items()):
			for (age_b, count_b) in list(age_groups.items()):
				if friendRequests(age_a, age_b):
					total_requests += count_a * count_b
					if age_a == age_b:
						total_requests -= count_a
		return total_requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		c = collections.Counter(ages)
		count = 0
		for a in c:
			for b in c:
				if self.request(a, b):
					continue
				count += c[a] * c[b]
				if a == b:
					count -= c[a]
		return count

	def request(self, a, b):
		return b <= 0.5 * a + 7 or b > a or a < 100 < b


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		counts = [0] * 121
		for age in ages:
			counts[age] += 1
		SUM = 0
		sums = []
		for c in counts:
			SUM += c
			sums.append(SUM)
		res = 0
		for age in range(15, 121):
			up = age
			down = age // 2 + 7
			res += counts[age] * (sums[up] - sums[down] - 1)
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		c = collections.Counter(ages)

		def request(x, y):
			return not (y <= 0.5 * x + 7 or (x < 100 and y > 100) or x < y)
		ans = 0
		for x in c:
			for y in c:
				if request(x, y):
					if x == y:
						ans += c[x] * (c[y] - 1)
					else:
						ans += c[x] * c[y]
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort(reverse=True)
		n = len(ages)

		def check(a, b):
			if b <= a * 0.5 + 7:
				return False
			if b > a:
				return False
			if b > 100 and a < 100:
				return False
			return True
		res = 0
		c = collections.Counter(ages)
		for a in c:
			for b in c:
				if check(a, b):
					res += c[a] * (c[b] - (a == b))
		return res


class Solution:

	def numFriendRequests(self, ages) -> int:
		ages = collections.Counter(ages)
		ans = 0
		for (ageA, countA) in list(ages.items()):
			for (ageB, countB) in list(ages.items()):
				if ageA * 0.5 + 7 >= ageB:
					continue
				if ageA < ageB:
					continue
				ans += countA * countB
				if ageA == ageB:
					ans -= countA
		return ans


import collections

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = 0
		table = collections.Counter(ages)
		for ageA in table:
			num_ = table[ageA]
			for ageB in table:
				if ageB <= 0.5 * ageA + 7:
					continue
				if ageB > ageA:
					continue
				if ageB > 100 and ageA < 100:
					continue
				if ageA != ageB:
					count += num_ * table[ageB]
				else:
					count += int(num_ * (num_ - 1))
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def helper(a, b):
			tmpB = a * 0.5 + 7
			return 0 if b <= tmpB or b > a or (b > 100 and a < 100) else 1
		(res, n) = (0, len(ages))
		if n == 1:
			return res
		counts = Counter(ages)
		for ageA in counts:
			for ageB in counts:
				(countA, countB) = (counts[ageA], counts[ageB])
				if helper(ageA, ageB):
					res += countA * countB
					if ageA == ageB:
						res -= countA
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = 0
		counter = [0] * 121
		for i in ages:
			counter[i] += 1
		for a in range(1, 121):
			for b in range(1, 121):
				if b > a:
					continue
				if b <= 0.5 * a + 7:
					continue
				if b > 100 and a < 100:
					continue
				count += counter[a] * counter[b]
				if a == b:
					count -= counter[a]
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:

		def cond(a, b):
			return not (b <= 0.5 * a + 7 or b > a or (b > 100 and a < 100))
		freq = Counter(ages).items()
		cnt = 0
		for (a, r) in freq:
			for (b, c) in freq:
				if cond(a, b):
					if a == b:
						cnt += r * (r - 1)
					else:
						cnt += r * c
		return cnt


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		counter = [0] * 121
		res = 0
		for a in ages:
			if a <= 14:
				continue
			counter[a] += 1
		for i in range(15, 121):
			for j in range(i + 1):
				if j <= 0.5 * i + 7:
					continue
				res += counter[i] * counter[j]
				if i == j:
					res -= counter[i]
		return res


import math
from collections import Counter

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		sol = 0
		c = Counter(ages)
		smaller_equal_age = [0]
		for i in range(1, 121):
			smaller_equal_age.append(smaller_equal_age[-1] + c[i])
		for i in range(15, 121):
			sol += c[i] * (smaller_equal_age[i] - 1 - smaller_equal_age[math.floor(0.5 * i + 7)])
		return sol


class Solution:

	def numFriendRequests(self, ages) -> int:
		ages = Counter(ages)
		ans = 0
		for (age_a, count_a) in ages.items():
			for (age_b, count_b) in ages.items():
				if age_a * 0.5 + 7 >= age_b:
					continue
				if age_a < age_b:
					continue
				if age_a < 100 and age_b > 100:
					continue
				ans += count_a * count_b
				if age_a == age_b:
					ans -= count_a
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = [0] * 121
		for a in ages:
			count[a] += 1
		for (i, val) in enumerate(count):
			count[i] = count[i - 1] + val
		total = 0
		for a in ages:
			ageMin = floor(0.5 * a + 8)
			ageMax = min(a, 120)
			ageMin = max(ageMin - 1, 0)
			total += max(count[ageMax] - count[ageMin] - 1, 0)
		return total


from collections import Counter

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		c = Counter(ages)
		return sum((self.can_be_friend(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c))

	def can_be_friend(self, age1, age2):
		if age2 <= 0.5 * age1 + 7 or age2 > age1 or (age2 > 100 and age1 < 100):
			return False
		return True


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		nums = [0] * 121
		for age in ages:
			nums[age] += 1
		ans = 0
		request = [set() for i in range(121)]
		for i in range(1, 121):
			for j in range(1, 121):
				if not (j <= i // 2 + 7 or j > i or (j > 100 and i < 100)):
					request[i].add(j)
		for i in range(1, 121):
			for j in request[i]:
				ans += nums[i] * (nums[j] if i != j else nums[j] - 1)
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = [0] * 121
		for age in ages:
			count[age] += 1
		res = 0
		for (ageA, countA) in enumerate(count):
			for (ageB, countB) in enumerate(count):
				if ageA * 0.5 + 7 >= ageB:
					continue
				if ageA < ageB:
					continue
				if ageA < 100 and ageB > 100:
					continue
				res += countA * countB
				if ageA == ageB:
					res -= countA
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		maxAge = 121
		preSum = [0] * maxAge
		from collections import Counter
		ageCnt = Counter(ages)
		for i in range(1, maxAge):
			preSum[i] += preSum[i - 1] + ageCnt[i]
		res = 0
		for age in range(15, maxAge):
			res += (preSum[age] - preSum[int(0.5 * age + 7)] - 1) * ageCnt[age]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		valid_ages = [0] * 121
		for age in ages:
			valid_ages[age] += 1
		count = 0
		for i in range(1, 121):
			ageA = valid_ages[i]
			for j in range(1, 121):
				ageB = valid_ages[j]
				if j <= 0.5 * i + 7 or j > i:
					continue
				if j > 100 and i < 100:
					continue
				count += ageA * ageB
				if i == j:
					count -= ageA
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()
		(ans, i, j) = (0, 0, 0)
		while i < len(ages):
			val = ages[i]
			while j < i and ages[j] <= 0.5 * val + 7:
				j += 1
			(cnt, num_equal) = (i - j, 0)
			while i < len(ages) and ages[i] == val:
				(num_equal, i) = (num_equal + 1, i + 1)
			ans += num_equal * cnt + num_equal * (num_equal - 1)
		return ans

	def numFriendRequests(self, ages):
		count = [0] * 121
		for age in ages:
			count[age] += 1
		ans = 0
		for (ageA, countA) in enumerate(count):
			for (ageB, countB) in enumerate(count):
				if ageA * 0.5 + 7 >= ageB:
					continue
				if ageA < ageB:
					continue
				ans += countA * countB
				if ageA == ageB:
					ans -= countA
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_counts = [0] * 121
		for age in ages:
			age_counts[age] += 1
		request_count = 0
		for (ageA, age_countA) in enumerate(age_counts):
			for (ageB, age_countB) in enumerate(age_counts):
				if ageB <= 0.5 * ageA + 7:
					continue
				if ageB > ageA:
					continue
				if ageA < 100 < ageB:
					continue
				request_count += age_countA * age_countB
				if ageA == ageB:
					request_count -= age_countA
		return request_count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = [0] * 121
		for age in ages:
			count[age] += 1
		res = 0
		for (age_a, count_a) in enumerate(count):
			for (age_b, count_b) in enumerate(count):
				if age_b <= 0.5 * age_a + 7:
					continue
				if age_b > age_a:
					continue
				if age_b > 100 and age_a < 100:
					continue
				res += count_a * count_b
				if age_a == age_b:
					res -= count_a
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = [0] * 121
		max_age = 0
		for age in ages:
			count[age] += 1
			max_age = max(max_age, age)
		ans = 0
		for (ageA, countA) in enumerate(count[:max_age + 2]):
			for (ageB, countB) in enumerate(count[:max_age + 2]):
				if ageA * 0.5 + 7 >= ageB:
					continue
				if ageA < ageB:
					continue
				if ageA < 100 < ageB:
					continue
				ans += countA * countB
				if ageA == ageB:
					ans -= countA
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		requests = 0
		ageCount = [0] * 121
		for age in ages:
			ageCount[age] += 1
		for A in range(120, 14, -1):
			if not ageCount[A]:
				continue
			requests += ageCount[A] * (ageCount[A] - 1)
			for B in range(A - 1, int(0.5 * A + 7), -1):
				requests += ageCount[A] * ageCount[B]
		return requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		a = sorted(ages)
		(i, j, k) = (0, 0, 0)
		ans = 0
		for i in range(1, len(a)):
			if a[i] <= 14:
				continue
			lb = a[i] * 0.5 + 7
			while a[j] <= lb:
				j += 1
			ans += i - j
			if a[k] != a[i]:
				k = i
			ans += i - k
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_dict = collections.Counter(ages)
		sorted_ages = sorted(age_dict.keys())
		requests = 0
		for i in sorted_ages:
			for j in sorted_ages:
				if j > 100 and i < 100 or j <= 0.5 * i + 7:
					continue
				if j > i:
					break
				if i == j:
					requests += age_dict[i] * (age_dict[j] - 1)
				else:
					requests += age_dict[i] * age_dict[j]
		return requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ageCounts = Counter(ages)
		numRequests = 0
		for a in range(1, 121):
			if ageCounts[a] > 0:
				exclLowerBound = 0.5 * a + 7
				lowerBound = ceil(exclLowerBound)
				if lowerBound == exclLowerBound:
					lowerBound += 1
				for a2 in range(lowerBound, a):
					numRequests += ageCounts[a2] * ageCounts[a]
				if lowerBound <= a:
					numRequests += ageCounts[a] * (ageCounts[a] - 1)
		return numRequests


class Solution:

	def check(self, a, b):
		if b <= 0.5 * a + 7:
			return False
		if b > a:
			return False
		if b > 100 and a < 100:
			return False
		return True

	def numFriendRequests(self, ages: List[int]) -> int:
		cnt = 0
		c = [0 for x in range(121)]
		for a in ages:
			c[a] += 1
		for i in range(len(c)):
			for j in range(len(c)):
				if self.check(i, j):
					cnt += c[i] * c[j]
					if i == j:
						cnt -= c[i]
		return cnt


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		dp = [0] * 121
		for i in ages:
			dp[i] += 1
		ans = 0
		mp = {}
		for i in range(15, 121):
			p = 0
			if dp[i] > 0:
				if i % 2 == 0:
					Min = int(i / 2 + 8)
				else:
					Min = int(math.ceil(i / 2 + 7))
				Max = i
				j = Min
				while j <= Max and j <= 120:
					if j == i:
						ans += dp[j] * (dp[j] - 1)
						p += dp[j] * (dp[j] - 1)
					else:
						ans += dp[i] * dp[j]
						p += dp[i] * dp[j]
					j += 1
				mp[i] = p
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		counts = Counter(ages)
		requests = 0
		conditions = [lambda ageA, ageB: 0.5 * ageA + 7 >= ageB, lambda ageA, ageB: ageA < ageB]

		def canSendRequest(ageA, ageB):
			return not any((condition(ageA, ageB) for condition in conditions))
		for (ageA, countA) in counts.items():
			for (ageB, countB) in counts.items():
				if canSendRequest(ageA, ageB):
					if ageA == ageB:
						requests += countA * (countA - 1)
					else:
						requests += countA * countB
		return requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ages.sort()
		right_most = {}
		for (ix, x) in enumerate(ages):
			right_most[x] = ix
		l = 0
		count = 0
		for (ix, x) in enumerate(ages):
			while ages[l] <= x / 2 + 7 and l < right_most[x]:
				l += 1
			count += right_most[x] - l
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = collections.Counter(ages)
		ans = 0
		for ageA in count:
			for ageB in count:
				countA = count[ageA]
				countB = count[ageB]
				if ageB <= ageA * 0.5 + 7:
					continue
				if ageA < ageB:
					continue
				ans += countA * countB
				if ageA == ageB:
					ans -= countA
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_count = Counter(ages)
		distinct_ages = set(age_count.keys())
		total_req = 0
		for a_age in distinct_ages:
			a_frn_req = 0
			for b_age in distinct_ages:
				if b_age > a_age or a_age < 100 < b_age or b_age <= 0.5 * a_age + 7:
					continue
				a_frn_req += age_count[a_age] * age_count[b_age]
				if a_age == b_age:
					a_frn_req -= age_count[a_age]
			total_req += a_frn_req
		return total_req


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		counts = collections.Counter(ages)
		valid = lambda A, B: not any([A * 0.5 + 7 >= B, A < B, A < 100 < B])
		count = 0
		items = list(counts.items())
		for (A, cntA) in items:
			for (B, cntB) in items:
				if valid(A, B):
					count += cntA * cntB
					if A == B:
						count -= cntA
		return count


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_count = [0] * 121
		for age in ages:
			age_count[age] += 1
		res = 0
		print(len(age_count))
		for i in range(121):
			for j in range(121):
				if age_count[i] > 0 and age_count[j] > 0:
					if j <= 0.5 * i + 7 or j > i:
						continue
					res += age_count[i] * age_count[j]
					if i == j:
						res -= age_count[i]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		agesCount = [0] * 121
		for age in ages:
			agesCount[age] += 1
		res = 0
		for i in range(1, 121):
			for j in range(1, 121):
				if agesCount[i] == 0 or agesCount[j] == 0 or j > i or (j > 100 and i < 100) or (j <= i / 2 + 7):
					continue
				res += agesCount[i] * agesCount[j]
				if i == j:
					res -= agesCount[i]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		age_library = {}
		for age in ages:
			age_library[age] = age_library.get(age, 0) + 1
		res = 0
		for (A, numA) in list(age_library.items()):
			for (B, numB) in list(age_library.items()):
				if not (B <= 0.5 * A + 7 or B > A or (B > 100 and A < 100)):
					res += numA * numB - numA * (A == B)
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		cnt = collections.Counter(ages)
		res = 0
		for p1 in cnt:
			for p2 in cnt:
				if p2 <= 0.5 * p1 + 7 or p2 > p1 or (p2 > 100 and p1 < 100):
					continue
				if p1 == p2:
					res += (cnt[p1] - 1) * cnt[p1]
				else:
					res += cnt[p1] * cnt[p2]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		if not ages:
			return 0
		agesToCount = [0] * 121
		for age in ages:
			agesToCount[age] += 1
		result = 0
		for ageA in range(1, 121):
			for ageB in range(1, 121):
				if ageB <= ageA and ageB > 0.5 * ageA + 7:
					if ageA == ageB:
						result += agesToCount[ageA] * (agesToCount[ageA] - 1)
					else:
						result += agesToCount[ageA] * agesToCount[ageB]
		return result


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		buckets = [0] * 121
		for age in ages:
			buckets[age] += 1
		ans = 0
		for i in range(1, 121):
			if buckets[i] <= 0:
				continue
			for j in range(1, 121):
				if buckets[j] <= 0:
					continue
				if j <= 0.5 * i + 7 or j > i or (j > 100 and i < 100):
					continue
				ans += buckets[i] * buckets[j]
				if i == j:
					ans -= buckets[i]
		return ans


from collections import Counter

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		if not ages:
			return 0

		def friend(A, B):
			if B > A:
				return False
			if B <= A * 0.5 + 7:
				return False
			return True
		counter = Counter(ages)
		requests = 0
		for (ageA, countA) in list(counter.items()):
			for (ageB, countB) in list(counter.items()):
				if friend(ageA, ageB):
					requests = requests + countA * countB if ageA != ageB else requests + (countA - 1) * countA
		return requests


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = Counter(ages)
		ans = 0
		for i in count:
			for j in count:
				if not (j <= i * 0.5 + 7 or j > i):
					ans += count[i] * count[j]
					if j == i:
						ans -= count[i]
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		count = collections.Counter(ages)
		ans = 0
		for (A, countA) in count.items():
			for (B, countB) in count.items():
				if B <= 0.5 * A + 7:
					continue
				elif B > A:
					continue
				elif B > 100 and A < 100:
					continue
				ans += countA * countB
				if A == B:
					ans -= countA
		return ans


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		ct = Counter(ages)
		res = 0
		for a in ct:
			for b in ct:
				if b <= 0.5 * a + 7:
					continue
				if b > a:
					continue
				res += ct[a] * ct[b] if a != b else ct[a] ** 2 - ct[a]
		return res


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		c = collections.Counter(ages)
		return sum((self.sendFriend(a, b) * c[a] * (c[b] - (a == b)) for a in c for b in c))

	def sendFriend(self, A, B):
		if B <= 0.5 * A + 7:
			return False
		if B > A:
			return False
		if B > 100 and A < 100:
			return False
		return True


class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		d = {}
		ans = 0
		for age in ages:
			if age not in d:
				d[age] = 1
			else:
				d[age] += 1
		print(d)
		for (ageA, countA) in list(d.items()):
			for (ageB, countB) in list(d.items()):
				print((ageA, countA, ageB, countB))
				if ageA * 0.5 + 7 >= ageB:
					continue
				if ageA < ageB:
					continue
				if ageA < 100 < ageB:
					continue
				if ageA != ageB:
					ans += countA * countB
				else:
					ans += (countA - 1) * countA
		return ans


import bisect

class Solution:

	def numFriendRequests(self, ages: List[int]) -> int:
		if not ages:
			return 0
		cnt = 0
		N = len(ages)
		ages.sort()
		for i in range(N):
			a = ages[i]
			if a <= 14:
				continue
			idx1 = bisect.bisect(ages, a)
			x = 0.5 * a + 7
			idx2 = bisect.bisect(ages, x)
			while idx2 < N and ages[idx2] == x:
				idx2 += 1
			cnt += max(0, idx1 - idx2 + (-1 if idx2 <= i <= idx1 else 0))
		return cnt