You are playing a computer game, where you lead a party of $m$ soldiers. Each soldier is characterised by his agility $a_i$.

The level you are trying to get through can be represented as a straight line segment from point $0$ (where you and your squad is initially located) to point $n + 1$ (where the boss is located).

The level is filled with $k$ traps. Each trap is represented by three numbers $l_i$, $r_i$ and $d_i$. $l_i$ is the location of the trap, and $d_i$ is the danger level of the trap: whenever a soldier with agility lower than $d_i$ steps on a trap (that is, moves to the point $l_i$), he gets instantly killed. Fortunately, you can disarm traps: if you move to the point $r_i$, you disarm this trap, and it no longer poses any danger to your soldiers. Traps don't affect you, only your soldiers.

You have $t$ seconds to complete the level — that is, to bring some soldiers from your squad to the boss. Before the level starts, you choose which soldiers will be coming with you, and which soldiers won't be. After that, you have to bring all of the chosen soldiers to the boss. To do so, you may perform the following actions:

  if your location is $x$, you may move to $x + 1$ or $x - 1$. This action consumes one second;  if your location is $x$ and the location of your squad is $x$, you may move to $x + 1$ or to $x - 1$ with your squad in one second. You may not perform this action if it puts some soldier in danger (i. e. the point your squad is moving into contains a non-disarmed trap with $d_i$ greater than agility of some soldier from the squad). This action consumes one second;  if your location is $x$ and there is a trap $i$ with $r_i = x$, you may disarm this trap. This action is done instantly (it consumes no time). 

Note that after each action both your coordinate and the coordinate of your squad should be integers.

You have to choose the maximum number of soldiers such that they all can be brought from the point $0$ to the point $n + 1$ (where the boss waits) in no more than $t$ seconds.


-----Input-----

The first line contains four integers $m$, $n$, $k$ and $t$ ($1 \le m, n, k, t \le 2 \cdot 10^5$, $n < t$) — the number of soldiers, the number of integer points between the squad and the boss, the number of traps and the maximum number of seconds you may spend to bring the squad to the boss, respectively.

The second line contains $m$ integers $a_1$, $a_2$, ..., $a_m$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the agility of the $i$-th soldier.

Then $k$ lines follow, containing the descriptions of traps. Each line contains three numbers $l_i$, $r_i$ and $d_i$ ($1 \le l_i \le r_i \le n$, $1 \le d_i \le 2 \cdot 10^5$) — the location of the trap, the location where the trap can be disarmed, and its danger level, respectively.


-----Output-----

Print one integer — the maximum number of soldiers you may choose so that you may bring them all to the boss in no more than $t$ seconds.


-----Example-----
Input
5 6 4 14
1 2 3 4 5
1 5 2
1 2 5
2 3 5
3 5 3

Output
3



-----Note-----

In the first example you may take soldiers with agility $3$, $4$ and $5$ with you. The course of action is as follows:

  go to $2$ without your squad;  disarm the trap $2$;  go to $3$ without your squad;  disartm the trap $3$;  go to $0$ without your squad;  go to $7$ with your squad. 

The whole plan can be executed in $13$ seconds.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
(M, N, K, T) = map(int, input().split())
A = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(K)]
A.append(10 ** 15)
A.sort(reverse=True)
l = 0
r = M + 1
while r - l > 1:
	m = (r + l) // 2
	D_limit = A[m]
	P = [0] * (N + 2)
	for (L, R, D) in LRD:
		if D_limit < D:
			P[L] += 1
			P[R + 1] -= 1
	c = 0
	for i in range(N + 1):
		P[i + 1] += P[i]
		if P[i + 1] > 0:
			c += 1
	time = N + 1 + 2 * c
	if time <= T:
		l = m
	else:
		r = m
print(l)


(m, n, k, t) = list(map(int, input().split()))
a = [0] + sorted(list(map(int, input().split()))) + [3 * 10 ** 5]
data = sorted([list(map(int, input().split())) for _ in range(k)])
ok = m + 1
ng = 0
while ok - ng > 1:
	mid = (ok + ng) // 2
	A = a[mid]
	interval_set = []
	for i in range(k):
		if data[i][2] <= A:
			continue
		if len(interval_set) == 0:
			interval_set.append([data[i][0], data[i][1]])
		elif interval_set[-1][1] < data[i][0]:
			interval_set.append([data[i][0], data[i][1]])
		elif interval_set[-1][1] < data[i][1]:
			new_interval = [interval_set.pop()[0], data[i][1]]
			interval_set.append(new_interval)
	time = n + 1
	for interval in interval_set:
		time += (interval[1] - interval[0] + 1) * 2
	if time <= t:
		ok = mid
	else:
		ng = mid
print(m - ok + 1)


import sys
input = sys.stdin.readline
import bisect
(m, n, k, t) = map(int, input().split())
ag = list(map(int, input().split()))
ag.sort()
lrd = [list(map(int, input().split())) for i in range(k)]
lrd.sort()
lf = 0
rg = m + 1
while lf + 1 < rg:
	x = (lf + rg) // 2
	agl = ag[m - x]
	lr = []
	for (l, r, d) in lrd:
		if d > agl:
			if lr and lr[-1][1] < l:
				lr.append([l, r])
			elif lr:
				lr[-1][1] = max(lr[-1][1], r)
			else:
				lr.append([l, r])
	ans = n + 1
	if lr:
		for (l, r) in lr:
			ans += (r - l + 1) * 2
	if ans > t:
		rg = x
	else:
		lf = x
print(lf)


from sys import stdin
(m, n, k, t) = [int(x) for x in stdin.readline().split()]
a = sorted([int(x) for x in stdin.readline().split()], reverse=True)
traps = []
for x in range(k):
	(l, r, d) = [int(x) for x in stdin.readline().split()]
	traps.append((d, l - 1, r))
traps.sort()
low = 0
high = m - 1
valid = -1
while low <= high:
	mid = (low + high) // 2
	agi = a[mid]
	time = t - n - 1
	line = [0 for x in range(n + 1)]
	for (d, l, r) in traps:
		if d > agi:
			line[l] += 1
			line[r] -= 1
	total = 0
	c = 0
	for x in line:
		c += x
		if c:
			total += 1
	time -= 2 * total
	if time >= 0:
		valid = max(valid, mid)
		low = mid + 1
	else:
		high = mid - 1
print(valid + 1)


import sys
input = sys.stdin.readline
(m, n, k, t) = map(int, input().split())
A = list(map(int, input().split()))
T = [tuple(map(int, input().split())) for i in range(k)]
seg_el = 1 << (n + 2).bit_length()
seg_height = 1 + (n + 2).bit_length()
SEG = [0] * (2 * seg_el)
LAZY = [0] * (2 * seg_el)

def indexes(L, R):
	INDLIST = []
	R -= 1
	L >>= 1
	R >>= 1
	while L != R:
		if L > R:
			INDLIST.append(L)
			L >>= 1
		else:
			INDLIST.append(R)
			R >>= 1
	while L != 0:
		INDLIST.append(L)
		L >>= 1
	return INDLIST

def updates(l, r, x):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY[ind] != None:
			update_lazy = LAZY[ind] * (1 << seg_height - 1 - ind.bit_length())
			LAZY[ind << 1] = LAZY[1 + (ind << 1)] = LAZY[ind]
			SEG[ind << 1] = SEG[1 + (ind << 1)] = update_lazy
			LAZY[ind] = None
	while L != R:
		if L > R:
			SEG[L] = x * (1 << seg_height - L.bit_length())
			LAZY[L] = x
			L += 1
			L //= L & -L
		else:
			R -= 1
			SEG[R] = x * (1 << seg_height - R.bit_length())
			LAZY[R] = x
			R //= R & -R
	for ind in UPIND:
		SEG[ind] = SEG[ind << 1] + SEG[1 + (ind << 1)]

def getvalues(l, r):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY[ind] != None:
			update_lazy = LAZY[ind] * (1 << seg_height - 1 - ind.bit_length())
			LAZY[ind << 1] = LAZY[1 + (ind << 1)] = LAZY[ind]
			SEG[ind << 1] = SEG[1 + (ind << 1)] = update_lazy
			LAZY[ind] = None
	ANS = 0
	while L != R:
		if L > R:
			ANS += SEG[L]
			L += 1
			L //= L & -L
		else:
			R -= 1
			ANS += SEG[R]
			R //= R & -R
	return ANS
T.sort(key=lambda x: x[2], reverse=True)
OK = 2 * 10 ** 5 + 1
ind = 0
for i in range(2 * 10 ** 5 + 2, -1, -1):
	while ind < k and T[ind][2] >= i:
		updates(T[ind][0], T[ind][1] + 1, 1)
		ind += 1
	if getvalues(0, n + 2) * 2 + n + 1 <= t:
		OK = i
	else:
		break
ANS = 0
for a in A:
	if a >= OK - 1:
		ANS += 1
print(ANS)


import os
import sys

def main():
	(M, N, K, T) = read_ints()
	A = read_ints()
	B = [tuple(read_ints()) for _ in range(K)]
	print(solve(M, N, K, T, A, B))

def solve(M, N, K, T, A, B):
	B.sort()

	def seconds(agi):
		traps = [(l, r) for (l, r, d) in B if d > agi]
		x = 0
		sec = 0
		sw = -1
		for (l, r) in traps:
			if sw != -1 and sw < l:
				sec += 2 * (sw - x)
				sw = -1
			if sw != -1:
				sw = max(sw, r)
				continue
			sec += l - 1 - x
			x = l - 1
			sw = r
		if sw != -1:
			sec += 2 * (sw - x)
		sec += N + 1 - x
		return sec
	min_agi = min(A)
	max_agi = max(A)
	if seconds(max_agi) > T:
		return 0
	if seconds(min_agi) <= T:
		return len(A)
	lb = min_agi
	ub = max_agi
	while ub - lb > 1:
		agi = (lb + ub) // 2
		if seconds(agi) > T:
			lb = agi
		else:
			ub = agi
	return len([a for a in A if a >= ub])
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def read_int():
	return int(inp())

def read_ints():
	return [int(e) for e in inp().split()]

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)
main()


(m, n, k, t) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
traps = [tuple(map(int, input().split())) for _ in range(k)]

def calc(ans):
	mina = a[ans - 1]
	tc = [0] * (n + 2)
	for (l, r, d) in traps:
		if mina < d:
			tc[l - 1] += 1
			tc[r] -= 1
	for i in range(1, n + 2):
		tc[i] += tc[i - 1]
	ans = 0
	for i in range(n + 2):
		if tc[i] > 0:
			ans += 1
	return ans * 2 + n + 1
(l, r) = (0, m + 1)
while r - l > 1:
	mid = (l + r) // 2 + (l + r) % 2
	if calc(mid) <= t:
		l = mid
	else:
		r = mid
print(l)


import sys
import math
from collections import defaultdict, Counter, deque
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')

def find(ind):
	ma = a[ind - 1]
	end = 0
	cur = n + 1
	for j in range(k):
		if l1[j][2] > ma:
			if end < l1[j][1]:
				cur += (l1[j][1] - end) * 2
				end = l1[j][1]
				if cur > t:
					return 0
		end = max(end, l1[j + 1][0] - 1)
	return 1
for i in range(1):
	(m, n, k, t) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	l1 = []
	for j in range(k):
		(l, r, d) = map(int, input().split())
		l1.append([l, r, d])
	l1.sort()
	l1.append([10 ** 8, 0, 0])
	l = 1
	r = m
	while l <= r:
		mid = (l + r) // 2
		if find(mid):
			l = mid + 1
		else:
			r = mid - 1
	print(r)


from sys import stdin
input = stdin.readline
(m, n, k, t) = map(int, input().split())
a = list(map(int, input().split()))
trap = []

def check(x):
	avg = a[-x]
	cost = n + 1
	nr = 0
	for i in range(k):
		(xx, y, d) = trap[i]
		if d <= avg:
			continue
		if y > nr:
			cost += (y - max(xx - 1, nr)) * 2
			nr = y
	return cost <= t
for i in range(k):
	trap.append(list(map(int, input().split())))
trap.sort()
a.sort()
l = 0
r = m + 1
while r - l > 1:
	mid = (l + r) // 2
	if check(mid):
		l = mid
	else:
		r = mid
print(l)


(m, n, k, t) = list(map(int, input().split()))
soldiers = list(map(int, input().split()))
traps = []
for _ in range(k):
	(l, r, d) = list(map(int, input().split()))
	traps.append((l, r, d))
soldiers.sort(reverse=True)
traps.sort()

def cost(count):
	agil = soldiers[count - 1] if count > 0 else 10 ** 6
	current_begin = 0
	current_end = -1
	inter_cost = 0
	for (l, r, d) in traps:
		if d <= agil:
			continue
		if l > current_end:
			inter_cost += 2 * (current_end - current_begin + 1)
			current_begin = l
		current_end = max(current_end, r)
	inter_cost += 2 * (current_end - current_begin + 1)
	return inter_cost + n + 1

def bin_search(lo, hi):
	if lo + 1 >= hi:
		return lo
	mid = (lo + hi) // 2
	if cost(mid) <= t:
		lo = mid
	else:
		hi = mid
	return bin_search(lo, hi)
result = bin_search(0, m + 1)
print(result)


import sys
input = sys.stdin.readline

def inter(a, b):
	if b[0] <= a[1]:
		return 1
	return 0

def check(le):
	if le == 0:
		return 1
	mi = it[le - 1]
	tr = [i[:2] for i in aaa if i[2] > mi]
	if tr == []:
		return 1
	aa = [tr[0][:]]
	for i in range(1, len(tr)):
		if inter(aa[-1], tr[i]):
			aa[-1][1] = max(aa[-1][1], tr[i][1])
		else:
			aa.append(tr[i][:])
	tt = 0
	a = 0
	for i in range(len(aa)):
		tt += aa[i][0] - 1 - a
		a = aa[i][0] - 1
		tt += 3 * (aa[i][1] - aa[i][0] + 1)
		a = aa[i][1]
	tt += n + 1 - a
	return tt <= t
(m, n, k, t) = map(int, input().split())
it = list(map(int, input().split()))
it.sort(reverse=True)
aaa = []
for i in range(k):
	(l, r, d) = map(int, input().split())
	aaa.append([l, r, d])
aaa.sort()
low = 0
high = m
while low < high - 1:
	mid = (low + high) // 2
	a = check(mid)
	if a:
		low = mid
	else:
		high = mid - 1
for i in range(high, low - 1, -1):
	if check(i):
		ans = i
		break
print(ans)


import sys
input = sys.stdin.readline

def checker(no):
	pivot = agility[-no]
	time = 0
	squad = 0
	captain = 0
	for i in range(len(specs)):
		if specs[i][2] <= pivot:
			continue
		elif captain < specs[i][0]:
			time += specs[i][0] - 1 - squad + (captain - squad) * 2
			(captain, squad) = (specs[i][1], specs[i][0] - 1)
		else:
			captain = max(captain, specs[i][1])
	if time > t:
		return False
	else:
		return True
(m, n, k, t) = map(int, input().split())
agility = [int(i) for i in input().split()]
specs = []
for i in range(k):
	(l, r, d) = map(int, input().split())
	specs.append([l, r, d])
specs.sort()
agility.sort()
specs.append([n + 2, n + 7, 10 ** 6])
beg = 0
last = m + 1
while last - beg > 1:
	mid = (beg + last) // 2
	count = checker(mid)
	if count:
		beg = mid
	else:
		last = mid
print(beg)


import sys
from bisect import bisect_left
(m, n, k, t) = map(int, input().split())
a = sorted(map(int, input().split()))
traps = sorted((list(map(int, l.split())) for l in sys.stdin))
(ok, ng) = (2 * 10 ** 5, 0)
while ok - ng > 1:
	mid = (ok + ng) // 2
	(l, r) = (0, 0)
	dist = n + 1
	for i in range(k):
		if mid < traps[i][2]:
			if r < traps[i][0]:
				dist += (r - l) * 2
				(l, r) = (traps[i][0] - 1, traps[i][1])
			else:
				r = max(r, traps[i][1])
	dist += (r - l) * 2
	if dist <= t:
		ok = mid
	else:
		ng = mid
print(m - bisect_left(a, ok))


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
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')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, m1, k, t) = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
d = []
for i in range(k):
	(a, b, c) = map(int, input().split())
	d.append((a, b, c))
d.sort()

def find(mid):
	if mid == 0:
		return True
	low = l[mid - 1]
	seg = []
	for i in d:
		if i[2] > low:
			seg.append((i[0], i[1]))
	time = m1 + 1
	cur = 0
	for i in seg:
		if i[1] <= cur:
			continue
		else:
			time += 2 * max(0, min(i[1] - cur, i[1] - i[0] + 1))
			cur = i[1]
	if time <= t:
		return True
	return False
ans = 0
st = 0
end = n
while st <= end:
	mid = (st + end) // 2
	if find(mid) == True:
		ans = mid
		st = mid + 1
	else:
		end = mid - 1
print(ans)


import sys

def army(weak, traps, t_max, n):
	t = n + 1
	alone = [0] * (n + 1)
	for (l, r, d) in traps:
		if d <= weak:
			break
		alone[l - 1] += 1
		alone[r] -= 1
	interval = 0
	for loc in range(n + 1):
		interval += alone[loc]
		if interval:
			t += 2
	return t <= t_max
reader = (list(map(int, s.split())) for s in sys.stdin)
(m, n, k, t_max) = next(reader)
a = list(next(reader))
traps = []
for _ in range(k):
	(l, r, d) = next(reader)
	traps.append((l, r, d))
a.sort(reverse=True)
traps.sort(key=lambda x: x[2], reverse=True)
L = 0
R = m + 1
while L + 1 < R:
	check = (L + R) // 2
	if army(a[check - 1], traps, t_max, n):
		L = check
	else:
		R = check
print(L)


(m, n, k, t) = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]
A.sort()
traps = []
for i in range(k):
	(l, r, d) = [int(s) for s in input().split()]
	traps.append((l, r, d))
traps.sort()

def canTake(agi):
	farest = 0
	trapIndex = 0
	wasteTime = 0
	while trapIndex < len(traps):
		trap = traps[trapIndex]
		if trap[2] <= agi:
			trapIndex += 1
			continue
		if trap[1] <= farest:
			trapIndex += 1
			continue
		newFarest = trap[1]
		if trap[0] > farest:
			wasteTime += (trap[1] - trap[0] + 1) * 2
		else:
			wasteTime += (newFarest - farest) * 2
		farest = newFarest
		trapIndex += 1
	if wasteTime + n + 1 > t:
		return False
	else:
		return True

def binSearch(A):
	if canTake(A[0]):
		return 0
	low = 0
	high = len(A)
	while high - low > 1:
		mid = (low + high) // 2
		if canTake(A[mid]):
			high = mid
		else:
			low = mid
	return high
firstCan = binSearch(A)
print(len(A) - firstCan)


(m, n, k, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
trap = list()
for i in range(k):
	(x1, x2, x3) = list(map(int, input().split()))
	trap.append([x1, x2, x3])
trap.sort()
a.sort()
x = -1
l = 0
r = len(a) - 1
s = 0
while r - l >= 0:
	x = (l + r) // 2
	weig = a[x]
	ltrap = 0
	rtrap = 0
	time = 0
	for i in trap:
		if i[2] > weig:
			if i[0] <= rtrap:
				rtrap = max(rtrap, i[1])
				time += i[0] - ltrap
				ltrap = i[0]
			else:
				time += rtrap - ltrap + 1
				rtrap = i[1]
				ltrap = i[0]
	time += rtrap - ltrap
	if 2 * time + n + 1 <= t:
		s = max(s, len(a) - x)
		r = x - 1
	else:
		l = x + 1
print(s)


import sys
from bisect import bisect_left
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
	ok = mx
	ng = mn
	while ng + 1 < ok:
		mid = (ok + ng) // 2
		if func(mid):
			ok = mid
		else:
			ng = mid
	return ok
(M, N, K, T) = MAP()
A = LIST()
LRD = []
for i in range(K):
	(l, r, d) = MAP()
	LRD.append((l, r, d))

def check(m):
	imos = [0] * (N + 2)
	for (l, r, d) in LRD:
		if d > m:
			imos[l] += 1
			imos[r + 1] -= 1
	imos = list(accumulate(imos))
	cnt = 0
	for i in imos:
		if i > 0:
			cnt += 1
	return cnt * 2 + N + 1 <= T
amx = max(A)
res = bisearch_min(0, amx + 1, check)
A.sort()
idx = bisect_left(A, res)
cnt = M - idx
print(cnt)


import sys
input = sys.stdin.readline
(m, n, k, t) = list(map(int, input().split()))
A = list(map(int, input().split()))
T = [tuple(map(int, input().split())) for i in range(k)]
NG = 0
OK = 2 * 10 ** 5 + 1
while OK - NG > 1:
	mid = (OK + NG) // 2
	USE = [0] * (2 * 10 ** 5 + 3)
	for (l, r, d) in T:
		if d >= mid:
			USE[l - 1] += 1
			USE[r] -= 1
	for i in range(1, 2 * 10 ** 5 + 3):
		USE[i] += USE[i - 1]
	if (2 * 10 ** 5 + 3 - USE.count(0)) * 2 + n + 1 <= t:
		OK = mid
	else:
		NG = mid
ANS = 0
for a in A:
	if a >= OK - 1:
		ANS += 1
print(ANS)


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
(M, N, K, T) = map(int, input().split())
SOL = list(map(int, input().split()))
SOL = sorted(SOL, reverse=True)
traps = [list(map(lambda x: int(x), input().split())) for _ in range(K)]
traps = sorted(traps, key=lambda x: (x[0], x[1]))
lower = 0
high = M
while lower <= high:
	mid = (lower + high) // 2
	lower_sol = SOL[mid - 1] if mid - 1 >= 0 else float('inf')
	add = 0
	right_most = 0
	for (l, r, d) in traps:
		if d <= lower_sol:
			continue
		elif l > right_most:
			add += r - l + 1
			right_most = r
		else:
			add += max(r - right_most, 0)
			right_most = max(r, right_most)
	cost = N + 1 + add * 2
	if cost <= T:
		lower = mid + 1
	else:
		high = mid - 1
print(lower - 1)


import sys
input = sys.stdin.readline
(m, n, k, t) = list(map(int, input().split()))
A = list(map(int, input().split()))
T = [tuple(map(int, input().split())) for i in range(k)]
A.sort(reverse=True)
SLIST = [0] * (2 * 10 ** 5 + 2)
ind = 0
for i in range(A[0], -1, -1):
	SLIST[i] = SLIST[i + 1]
	while ind < m and A[ind] == i:
		SLIST[i] += 1
		ind += 1
SLIST = [SLIST[0]] + SLIST
NG = 0
OK = 2 * 10 ** 5 + 1
while OK - NG > 1:
	mid = (OK + NG) // 2
	USE = [0] * (2 * 10 ** 5 + 3)
	for (l, r, d) in T:
		if d >= mid:
			USE[l - 1] += 1
			USE[r] -= 1
	for i in range(1, 2 * 10 ** 5 + 3):
		USE[i] += USE[i - 1]
	if (2 * 10 ** 5 + 3 - USE.count(0)) * 2 + n + 1 <= t:
		OK = mid
	else:
		NG = mid
print(SLIST[OK])


class Traps:

	def __init__(self, l, r, d):
		self.before_l = l - 1
		self.r = r
		self.d = d

def qujianbingji(x, y):
	if y[0] < x[0]:
		if y[1] < x[0]:
			return [y, x]
		elif y[1] <= x[1]:
			z = [y[0], x[1]]
			return [z]
		else:
			return [y]
	elif y[0] < x[1]:
		if y[1] <= x[1]:
			return [x]
		else:
			z = [x[0], y[1]]
			return [z]
	else:
		return [x, y]

def main():
	(m, n, k, t) = map(int, input().split())
	lista = list(map(int, input().split()))
	lista.sort(reverse=True)
	list_traps = []
	for i in range(k):
		(l, r, d) = map(int, input().split())
		list_traps.append(Traps(l, r, d))
	list_traps.sort(key=lambda x: x.before_l)
	T = 0
	(left, right) = (-1, m)
	while right - left > 1:
		dangerous_traps = []
		mid = (left + right) // 2
		for trap in list_traps:
			if trap.d > lista[mid]:
				dangerous_traps.append(trap)
		if dangerous_traps == []:
			T = n + 1
		else:
			space = 0
			finalbing = [[dangerous_traps[0].before_l, dangerous_traps[0].r]]
			for dangerous_trap in dangerous_traps:
				c = qujianbingji(finalbing[-1], [dangerous_trap.before_l, dangerous_trap.r])
				del finalbing[-1]
				if len(c) == 2:
					finalbing.append(c[0])
					finalbing.append(c[1])
				else:
					finalbing.append(c[0])
			lenfb = len(finalbing)
			if lenfb == 1:
				T = n + 1 + (finalbing[0][1] - finalbing[0][0]) * 2
			else:
				for x in range(lenfb - 1):
					space += finalbing[x + 1][0] - finalbing[x][1]
				maxlen = finalbing[-1][1] - finalbing[0][0]
				T = n + 1 + 2 * (maxlen - space)
		if T > t:
			(left, right) = (left, mid)
			count = mid
		else:
			(left, right) = (mid, right)
			count = mid + 1
	print(count)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()

def chk(a):
	Y = [0] * (N + 10)
	for (l, r, d) in X:
		if d <= a:
			continue
		Y[l - 1] += 1
		Y[r] -= 1
	for i in range(1, N + 10):
		Y[i] += Y[i - 1]
	return 1 if sum([min(Y[i], 1) for i in range(N + 5)]) * 2 + N + 1 <= T else 0
(M, N, K, T) = map(int, input().split())
A = [int(a) for a in input().split()]
X = []
for _ in range(K):
	(l, r, d) = map(int, input().split())
	X.append((l, r, d))
(l, r) = (0, 2 * 10 ** 5)
while r - l > 1:
	m = (l + r) // 2
	if chk(m):
		r = m
	else:
		l = m
print(len([a for a in A if a >= r]))


import sys
input = sys.stdin.readline
(sol_n, n, trap_n, t) = [int(item) for item in input().split()]
sold = [int(item) for item in input().split()]
sold.sort(reverse=True)
trap = []
for i in range(trap_n):
	(l, r, d) = [int(item) for item in input().split()]
	trap.append((d, l, r))
trap.sort()
ll = 0
rr = sol_n + 1
while rr - ll > 1:
	mid = (ll + rr) // 2
	to_save = sold[mid - 1]
	alone_walk = [0] * (n + 1)
	for (d, l, r) in trap:
		if d > to_save:
			alone_walk[l - 1] += 1
			alone_walk[r] -= 1
	total = 0
	time = 0
	for item in alone_walk:
		total += item
		if total > 0:
			time += 2
	time += n + 1
	if time <= t:
		ll = mid
	else:
		rr = mid
print(ll)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_str():
	return list(sys.stdin.readline().split())
(M, N, K, T) = inpl()
AA = inpl()
DD_di = []
LR = []
for i in range(K):
	(L, R, D) = inpl()
	LR.append((L, R))
	DD_di.append((D, i))
DD_di.sort()
DD_d = [D for (D, i) in DD_di]

def solve(x):
	idx = bisect.bisect_right(DD_d, x)
	path = [0] * (N + 2)
	for (D, i) in DD_di[idx:]:
		(L, R) = LR[i]
		path[L] += 1
		path[R + 1] -= 1
	t = N + 1
	bp = path[0]
	for i in range(1, N + 2):
		p = bp + path[i]
		if p > 0:
			t += 2
		bp = p
	return t <= T
OK = 10 ** 5 * 2 + 10
NG = -1
while OK - NG > 1:
	mid = (OK + NG) // 2
	if solve(mid):
		OK = mid
	else:
		NG = mid
ans = 0
for A in AA:
	if A >= OK:
		ans += 1
print(ans)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_str():
	return list(sys.stdin.readline().split())
(m, n, k, T) = list(map(int, input().split()))
a = list(map(int, input().split()))
DD = []
LR = []
for i in range(k):
	(L, R, D) = map(int, input().split())
	LR.append((L, R))
	DD.append((D, i))
DD.sort()
DD_id = [D for (D, i) in DD]

def Solve(x):
	idx = bisect.bisect_right(DD_id, x)
	path = [0] * (n + 2)
	for (X, i) in DD[idx:]:
		(LL, RR) = LR[i]
		path[LL] += 1
		path[RR + 1] -= 1
	t = n + 1
	bp = path[0]
	for i in range(1, n + 2):
		p = bp + path[i]
		if p > 0:
			t += 2
		bp = p
	return t <= T
L = -1
R = 2 * 10 ** 5 + 2
while R - L > 1:
	mid = (L + R) // 2
	if Solve(mid):
		R = mid
	else:
		L = mid
ans = 0
for i in a:
	if i >= R:
		ans += 1
print(ans)


import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def gcd(u, v):
	while v:
		(u, v) = (v, u % v)
	return u

def solve():
	(m, n, k, t) = nm()
	a = nl()
	trap = [tuple(nm()) for _ in range(k)]
	idx = 0
	trap.sort()
	ok = max(a) + 1
	ng = -1
	while ok - ng > 1:
		mid = (ok + ng) // 2
		imos = [0] * (n + 1)
		ctp = list()
		for (l, r, d) in trap:
			if d <= mid:
				continue
			if not ctp or ctp[-1][1] < l:
				ctp.append([l, r])
			else:
				ctp[-1][1] = max(ctp[-1][1], r)
		cost = n + 1
		for (l, r) in ctp:
			cost += (r - l + 1) * 2
		if cost > t:
			ng = mid
		else:
			ok = mid
	print(sum((1 for x in a if x >= ok)))
	return
solve()


import sys
from bisect import bisect_left

def get_time(pwr, cs, goal):
	length = 0
	cnt = 0
	(b, e) = (None, None)
	for (l, r, _) in filter(lambda x: x[0] <= x[1] and x[2] > pwr, cs):
		if not (b and e):
			(b, e) = (l, r)
			continue
		if l <= e:
			e = max(e, r)
		else:
			cnt += 1
			length += e - b
			(b, e) = (l, r)
	if b:
		cnt += 1
		length += e - b
	return goal + (length + cnt) * 2

def search(cs, goal, time, mn, mx):
	(l, r) = (mn, mx)
	while l <= r:
		m = (r + l) // 2
		t = get_time(m, cs, goal)
		if t < time:
			r = m - 1
		else:
			l = m + 1
	return l

def solve(cs, goal, solgers, time):
	solgers.sort()
	(mn, mx) = (solgers[0], solgers[-1])
	cs.sort()
	min_pow = search(cs, goal, time, mn, mx)
	return len(solgers) - bisect_left(solgers, min_pow)
lines = sys.stdin.readlines()
(m, n, k, t) = map(int, lines[0].split())
aa = list(map(int, lines[1].split()))
catches = []
for line in lines[2:]:
	(l, r, d) = map(int, line.split())
	if l <= r:
		catches.append((l, r, d))
catches.sort()
print(solve(catches, n, aa, t))


def main():
	import sys
	import bisect
	input = sys.stdin.buffer.readline
	(M, N, k, T) = map(int, input().split())
	a = list(map(int, input().split()))
	a.append(2 * 10 ** 5 + 1)
	a.sort(reverse=True)
	road = [[] for _ in range(N + 1)]
	for _ in range(k):
		(l, r, d) = map(int, input().split())
		road[l].append((r, d))
	ok = 0
	ng = M + 1
	mid = (ok + ng) // 2
	while ng - ok > 1:
		d_min = a[mid]
		flg = 0
		rmax = 0
		t = 1
		for i in range(1, N + 1):
			for (r, d) in road[i]:
				if d > d_min:
					flg = 1
					rmax = max(r, rmax)
			if i > rmax:
				flg = 0
			if flg:
				t += 3
			else:
				t += 1
		if t > T:
			ng = mid
		else:
			ok = mid
		mid = (ok + ng) // 2
	print(ok)
main()


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t
mini = 10 ** 18

def can(mid):
	ans = 0
	l = r = 0
	for i in range(k):
		if a[i][2] <= mid:
			continue
		if a[i][0] > r:
			ans += (r - l) * 3 + (a[i][0] - 1 - r)
			l = a[i][0] - 1
			r = a[i][1]
		else:
			r = max(r, a[i][1])
	ans += (r - l) * 3 + (n + 1 - r)
	return ans <= T
while t > 0:
	t -= 1
	(m, n, k, T) = mi()
	a = []
	b = li()
	b.sort(reverse=True)
	for i in range(k):
		(l, r, d) = mi()
		a.append([l, r, d])
	a.sort()
	l = ans = 0
	r = m - 1
	while l <= r:
		mid = (l + r) // 2
		if can(b[mid]):
			ans = mid + 1
			l = mid + 1
		else:
			r = mid - 1
	print(ans)


import sys
input = sys.stdin.readline

def check(num):
	count = 0
	prev = 0
	for i in trap:
		if i[2] > num:
			if i[0] <= prev:
				count += max(0, i[1] - prev)
				prev = max(prev, i[1])
			else:
				count += i[1] - i[0] + 1
				prev = i[1]
	count = count * 2 + n + 1
	if count <= t:
		return True
	return False
(m, n, k, t) = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
trap = []
for i in range(k):
	trap.append(tuple(map(int, input().split())))
trap.sort()
low = 0
high = m
while low < high:
	mid = (low + high) // 2
	if check(a[mid]):
		low = mid + 1
	else:
		high = mid - 1
if low < m and check(a[low]):
	print(low + 1)
else:
	print(low)


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(m, n, k, t) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
trap = []
for i in range(k):
	(li, ri, di) = [int(i) for i in input().split()]
	trap.append([di, li, ri])
trap.sort(reverse=1)
x = t - n - 1
y = x // 2
cnt = 0
ind = k
mm = 0
vis = [0] * (n + 2)
pvis = [0] * (n + 2)
for i in range(k):
	j = trap[i][1]
	while j <= trap[i][2]:
		if vis[j] == 0:
			vis[j] = max(vis[j], trap[i][2])
			cnt += 1
		else:
			j = vis[j]
		j += 1
	if cnt > y:
		ind = i - 1
		break
maxi = -1
if ind + 1 < len(trap):
	maxi = trap[ind + 1][0]
ans = 0
for i in range(m):
	if a[i] >= maxi:
		ans += 1
print(ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = int(1000000000.0) + 7
INF = float('inf')
(m, n, k, t) = mdata()
a = sorted(mdata())
trap = sorted([mdata() for i in range(k)], key=lambda x: x[0])
t -= n + 1
(start, end) = (0, m - 1)
while start <= end:
	mid = (start + end) // 2
	walk = 0
	(i, j) = (-1, -2)
	for (l, r, d) in trap:
		if d > a[mid]:
			if l <= j:
				j = max(r, j)
			else:
				walk += j - i + 1
				(i, j) = (l, r)
	walk += j - i + 1
	if 2 * walk <= t:
		end = mid - 1
	else:
		start = mid + 1
out(m - end - 1)


import sys
input = sys.stdin.buffer.readline

def movesRequired(agility):
	nMoves = n + 1
	repeatedIntervals = []
	for (l, r, d) in traps:
		if d > agility:
			if repeatedIntervals and repeatedIntervals[-1][1] >= l:
				repeatedIntervals[-1][1] = max(repeatedIntervals[-1][1], r)
			else:
				repeatedIntervals.append([l, r])
	for (l, r) in repeatedIntervals:
		nMoves += (r - l + 1) * 2
	return nMoves
(m, n, k, t) = [int(x) for x in input().split()]
traps = []
a = [int(x) for x in input().split()]
maxD = -1
for _ in range(k):
	(l, r, d) = [int(x) for x in input().split()]
	traps.append([l, r, d])
	maxD = max(maxD, d)
traps.sort(key=lambda x: x[0])
b = maxD + 1
largestImpossible = -1
while b > 0:
	while True:
		moves = movesRequired(largestImpossible + b)
		if moves > t:
			largestImpossible += b
		else:
			break
	b //= 2
smallestPossible = largestImpossible + 1
a.sort()
ans = 0
for i in range(m - 1, -1, -1):
	if a[i] >= smallestPossible:
		ans += 1
print(ans)


from sys import stdin
input = stdin.readline

def works(mid):
	ag = A[-mid]
	MAX = 0
	cur = 0
	out = N + 1
	for (l, r, d) in traps:
		if d <= ag:
			continue
		if l > MAX:
			out += (MAX - cur) * 2
			(MAX, cur) = (r, l - 1)
		else:
			MAX = max(MAX, r)
	return out <= time
(S, N, T, time) = map(int, input().split())
A = list(map(int, input().split()))
traps = [tuple(map(int, input().split())) for _ in range(T)]
traps.sort()
traps.append((N + 2, N + 5, 10 ** 6))
A.sort()
lo = 0
hi = S + 1
while hi - lo > 1:
	mid = (hi + lo) // 2
	if works(mid):
		lo = mid
	else:
		hi = mid
print(lo)


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, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

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

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			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 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
		self.size = n
		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):
		if r == self.size:
			r = self.num
		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 gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(m, n, k, t) = mi()
A = li()
A.sort()
trap = [tuple(mi()) for i in range(k)]

def cond(x):
	D = A[m - x]
	check = [0 for i in range(n + 2)]
	for (l, r, d) in trap:
		if d > D:
			check[l - 1] += 1
			check[r + 1] -= 1
	for i in range(1, n + 2):
		check[i] += check[i - 1]
	tmp = n + 1
	for i in range(1, n + 1):
		if check[i]:
			if check[i - 1]:
				if not check[i + 1]:
					tmp += 2 * i
			elif check[i + 1]:
				tmp -= 2 * i
	return tmp <= t
ok = 0
ng = m + 1
while ng - ok > 1:
	mid = (ng + ok) // 2
	if cond(mid):
		ok = mid
	else:
		ng = mid
print(ok)


import sys
input = sys.stdin.readline

def judge(x):
	cnt = [0] * (n + 2)
	for (l, r, d) in lrd:
		if x < d:
			cnt[l] += 1
			cnt[r + 1] -= 1
	for i in range(1, n + 2):
		cnt[i] += cnt[i - 1]
	sec = 0
	for i in range(1, n + 2):
		if cnt[i] == 0:
			sec += 1
		else:
			sec += 3
	return sec <= t

def binary_search():
	(l, r) = (0, m - 1)
	while l <= r:
		mid = (l + r) // 2
		if judge(a[mid]):
			r = mid - 1
		else:
			l = mid + 1
	return l
(m, n, k, t) = map(int, input().split())
a = list(map(int, input().split()))
lrd = [tuple(map(int, input().split())) for _ in range(k)]
a.sort()
print(m - binary_search())


from sys import stdin, stdout
from collections import deque
from bisect import bisect_left
(m, n, k, t) = map(int, stdin.readline().split())
soldiers = list(map(int, stdin.readline().split()))
dangers = []
points = []
for _ in range(k):
	(l, r, d) = map(int, stdin.readline().split())
	dangers.append(d)
	points.append((l, r, d))
soldiers.sort()
dangers.sort()
points.sort()

def gettime(d):
	total = 0
	cur = None
	for p in filter(lambda x: x[2] >= d, points):
		if not cur:
			total += p[1] - p[0] + 1
			cur = p[1]
		elif p[1] <= cur:
			continue
		elif p[0] > cur:
			total += p[1] - p[0] + 1
			cur = p[1]
		else:
			total += p[1] - cur
			cur = p[1]
	return total * 2
t -= n + 1
(i, j) = (0, k)
minlevel = 0
while True:
	k = i + (j - i) // 2
	if gettime(dangers[k]) > t:
		if i == k:
			minlevel = dangers[k]
			break
		else:
			i = k
	elif j == k:
		if k == 0:
			minlevel = 0
		else:
			minlevel = dangers[k - 1]
		break
	else:
		j = k
i = bisect_left(soldiers, minlevel)
stdout.write('{}\n'.format(m - i))