micro-and-array-1

Micro's friend Ravi gifted him a game called Array on his birthday. The game involves an array of distinct numbers of size N . The game follows 1-based indexing of array. Player has to perform Q operation on the array. The operation can be of following two types:
1. 0 x y : Update the xth element of array to y.
2. 1 v: Find the position of first element which is greater than or equal to v, and if there is no element greater than or equal to v then answer is -1.
Now as we know Micro is a programmer, so he thought of making a program for it but he got stuck and asked for your help.

Input:
First line consists of two space separated integers N and Q.
Second line contains N space separated integers.
Then Q lines follow each containing an operation.

Output:
For each operation of type 1 print the answer in a new line. 

Constraint:
1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ x ≤ N
1 ≤ Elements of array, y, v ≤ 200000
At any instant all the elements in array are distinct.

SAMPLE INPUT
5 4
5 4 3 2 1
1 4
1 6
0 3 7
1 6

SAMPLE OUTPUT
1
-1
3

Explanation

First element greater than or equal to 4 is 5 whose position is 1.
There is no element in the array which greater than or equal to 6 so answer is -1
After third operation the array becomes 5 4 7 2 1.
First element greater than or equal to 6 is now 7 whose position is 3.

Source: hackerearth | Difficulty: EASY
Tags: Range queries

Segment trees revisited


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
nNq  = input().split()
n = int(nNq[0])
q = int(nNq[1])
 
arr = input().split()
arr_ops = []
for i in range(q):
	arr_ops.append(input().split())

 
def doSmOp(arr,new_arr_op):
	count = 1
	for i in arr:
		if( int(i) >=  int(new_arr_op[1])):
			return count
		count+=1
	return -1
 
for new_arr_op in arr_ops:
	if( len(new_arr_op)==2):
		print(doSmOp(arr,new_arr_op))
	else:
		index_val = int(new_arr_op[1]) -1
		arr[index_val] = new_arr_op[2]

	
	



nNq  = input().split()
n = int(nNq[0])
q = int(nNq[1])

arr = input().split()
arr_ops = []
for i in range(q):
	arr_ops.append(input().split())
# start process

def doSmOp(arr,new_arr_op):
	count = 1
	for i in arr:
		if( int(i) >=  int(new_arr_op[1])):
			return count
		count+=1
	return -1

for new_arr_op in arr_ops:
	if( len(new_arr_op)==2):
		# do operation
		print(doSmOp(arr,new_arr_op))
	else:
		# do swap operation
		index_val = int(new_arr_op[1]) -1
		arr[index_val] = new_arr_op[2]
		# print new_arr_op[2]


n,q=list(map(int,input().split()))
arr=list(map(int,input().split()))
length=len(arr)
for i in range(1,q+1):
	flag=1
	inp=list(map(int,input().split()))
	if inp[0]==1:
		for j in range(0,length-1):
			if(arr[j]>=inp[1]):
				flag=0
				print(j+1)
				break;
		if flag==1:
			print('-1');
	else:
		arr[inp[1]-1]=inp[2];
	
		


n,q=list(map(int,input().split()))
arr=list(map(int,input().split()))
length=len(arr)
for i in range(1,q+1):
	flag=1
	inp=list(map(int,input().split()))
	if inp[0]==1:
		for j in range(0,length-1):
			if(arr[j]>=inp[1]):
				flag=0
				print(j+1)
				break;
		if flag==1:
			print('-1');
	else:
		arr[inp[1]-1]=inp[2];
	
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def findValue(input_data=[],value=0):
	count = 1
	index = -1
	for i in input_data:
		if i >= value:
			index = count
			break
		count += 1
	return index


n,q = list(map(int,input().split()))
input_data = list(map(int,input().split()))
for i in range(q):
	input_operation = list(map(int,input().split()))
	if len(input_operation) == 2:
		print(findValue(input_data = input_data, value = input_operation[1]))
	else:
		input_data[input_operation[1]-1] = input_operation[2]


N,Q = list(map(int, input().split()))
array = list(map(int, input().split()))

for i in range(Q):
	op = list(map(int, input().split()))
	if len(op) == 2:
		try:
			out = next(n[0] for n in enumerate(array) if n[1] >= op[1] )
			print((out+1))
		except:
			print((-1))
	else:
		array[op[1]-1] = op[2]


first_input = list(map(int, input().split()))
N, Q = first_input[0], first_input[1]
given_array = list(map(int, input().split()))

def update_array(input_array, given_array):
	if input_array[1] < len(given_array):
		given_array[input_array[1] - 1] = input_array[2]

for _ in range(Q):
	operation_input = list(map(int, input().split()))
	if len(operation_input) > 2:
		update_array(operation_input, given_array)
	else:
		for i, item in enumerate(given_array):
			ind = None
			if item >= operation_input[1]:
				ind = i + 1
				break
		if ind:
			print(ind)
		else:
			print(-1)


N , Q = list(map(int, input().split()))
arr = list(map(int, input().split()))


def update(x,y):
	global arr
	arr[x-1] = y

def disp(x):
	global arr
	for i in range(N):
		if arr[i] >= x:
			print(i+1)
			return
	print(-1)

for x in range(Q):
	querry = list(map(int, input().split()))
	if querry[0] == 0:
		update(querry[1],querry[2])
	if querry[0] == 1:
		disp(querry[1])


import sys

'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

array = []


class InvalidInput(Exception):
	pass


def _read_operation(string):
	splits = list(map(int, string.split()))
	code = splits[0]
	if code == 0:
		x, y = splits[1:]
		if x > len(array):
			raise InvalidInput('Maximum expected index: {};\t Given index: {}'.format(len(array), x))
		return (code, x, y)

	elif code == 1:
		return (code, splits[1])

	else:
		raise InvalidInput('Expected operation code: (0,1);\t Given operation code: {}'.format(code))


def _create_array(string):
	arr = []
	for item in string.split():
		arr.append(int(item))

	return arr


def replace(x, y):
	array[x - 1] = y


def find_greater(v):
	pos = -1

	for index, el in enumerate(array):
		if el >= v:
			pos = index + 1
			break

	print(pos)


def _execute(op):
	if op[0] == 0:
		replace(op[1], op[2])
	elif op[0] == 1:
		find_greater(op[1])

if __name__ == '__main__':

	input = sys.stdin.readline()
	array_len, num_of_operations = _create_array(input)

	input = sys.stdin.readline()
	array = _create_array(input)
	if len(array) != array_len:
		raise InvalidInput('Expected array length: {};\tGiven array length: {}'.format(array_len, len(array)))

	operations = []
	for i in range(num_of_operations):
		input = sys.stdin.readline()
		operations.append(_read_operation(input))

	list(map(_execute, operations))


n , q = input().replace('/r','').split(' ')
l= input().replace('/r','').split(' ')
for _ in range(int(q)):
	inp = input().replace('/r','').split(' ')
	for i in range(len(inp)):
		inp[i]=int(inp[i])
		
	if inp[0] is 0:
		l[inp[1]-1]=  inp[2]
	if inp[0] is 1:
		flg=-1
		for j in range(int(n)):
			if int(l[j]) >= inp[1] : 
				flg=j+1                
				break;
		print(flg)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
if __name__ == '__main__':
	n,q = list(map(int,input().split()))#n - size of array,q - operations
	a = list(map(int,input().split()))
	for i in range(q):
		op = list(map(int,input().split()))
		if op[0] == 0:
			a[op[1]-1] = op[2]
		elif op[0] == 1:
			found = 0
			for i,item in enumerate(a):
				if item >= op[1]:
					print(i+1)
					found = 1
					break
			if found == 0:
				print(-1)
	


n,q = [int (i) for i in input().strip().split()]
arr = [int (i) for i in input().split()]
for i in range(q):
	flag = False
	query = [int (i) for i in input().split()]
	if query[0] == 0:
		temp = query[1]-1
		arr[temp] = query[2]
	else:
		temp = query[1]
		for a_i in arr:
			if temp <= a_i:
				print((1+arr.index(a_i)))
				flag = True
				break
				
		if flag == False:
			print ('-1')


arr = list(map(int,input().strip().split()))
arr1 = list(map(int,input().strip().split()))
s= []
for i in range(arr[1]):
	arr2 = list(map(int,input().strip().split()))
	s.append(arr2)
for entry in s:
	if entry[0] == 0:
		arr1[entry[1]-1] = entry[2]
	elif entry[0] == 1:
		try:
			index=next(x[0] for x in enumerate(arr1) if x[1] >= entry[1])
			print(index+1)
		except:
			print(-1)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math

def retrieve(heap, value):
	indC = 1
	valP = -1
	while indC<heap.__len__() and heap[indC] >= value:
		if 2*indC+1<heap.__len__() and heap[2*indC] < value and heap[indC]==heap[indC*2+1]:
			indC = 2 * indC + 1
			valP = heap[indC]
			continue
		valP = heap[indC]
		indC = 2 * indC

	return valP

def update(tree, ind, value, twoPow, hashedIndexLocations):
	indT = int(ind + twoPow - 1)

	hashedIndexLocations[tree[indT]] = -1
	hashedIndexLocations[value] = ind

	tree[indT] = value
	indC = indT
	while indC>0:
		indP = int(indC/2)
		parentPrev = tree[indP]
		tree[indP] = max(tree[indP*2], tree[indP*2+1])
		if parentPrev == tree[indP]:
			break
		else:
			indC = indP

def treeC(theArray):
	twoPow = math.pow(2, math.ceil(math.log(theArray.__len__(), 2)))
	theArray.extend([-1] * (int(twoPow - theArray.__len__())))

	lC = theArray.__len__()
	#Initialize tree array
	tree= [-1] * lC
	tree.extend(theArray)

	for i in range (lC-1,0,-1):
		if 2*i+1 < tree.__len__()-1:
			tree[i] = max(tree[2*i+1], tree[2*i])
		else:
			tree[i] = tree[2*i]
	return tree, twoPow

def mainworker(N, arr, Q):
	hashedIndexLocations = {-1:-1}
	for i in range(arr.__len__()):
		hashedIndexLocations[arr[i]] = i+1

	heap, twoPow = treeC(arr)
	while Q >0:
		Q -=1
		# print ' query is' , query, 'end' ,
		x = list(map(int, input().split()))
		if x[0] == 0:
			update(heap, x[1], x[2], twoPow, hashedIndexLocations)
		elif x[0] == 1:
			print(hashedIndexLocations[retrieve(heap, x[1])])

N, Q = input().split()
arr = list(map(int, input().split()))

mainworker(N, arr, int(Q))



import math
from io import StringIO

def show_tree(tree, total_width=33, fill=' '):
	"""Pretty-print a tree."""
	output = StringIO()
	last_row = -1
	for i, n in enumerate(tree):
		if i:
			row = int(math.floor(math.log(i+1, 2)))
		else:
			row = 0
		if row != last_row:
			output.write('\n')
		columns = 2**row
		col_width = int(math.floor((total_width * 1.0) / columns))
		output.write(str(n).center(col_width, fill))
		last_row = row
	print(output.getvalue())
	print('-' * total_width)
	print()
	return


def create_tree(arr):
	next_power_of_two = math.pow(2,math.ceil(math.log(arr.__len__(), 2)))
	#print next_power_of_two
	arr.extend([-1]*(int(next_power_of_two-arr.__len__())))
	# show_tree(arr, 100)

	leafCount = arr.__len__()

	#Initialize tree array
	tree= [-1] * (leafCount)
	tree.extend(arr)

	#print tree

	for i in range (leafCount-1,0,-1):
		#print i
		if 2*i+1 < tree.__len__()-1:
			#print 2*i+1, 2*i
			tree[i] = max(tree[2*i+1], tree[2*i])
		else:
			tree[i] = tree[2*i]

	#print tree
	#show_tree(tree[1:], 50)

	return tree, next_power_of_two

def update(tree, index, value, offset, index_hash):
	tree_index = int(index+offset-1)

	index_hash[tree[tree_index]] = -1
	index_hash[value] = index

	tree[tree_index] = value
	cur_index = tree_index
	while cur_index>0:
		parent_index = int(cur_index/2)
		old_parent_value = tree[parent_index]
		tree[parent_index] = max(tree[parent_index*2], tree[parent_index*2+1])
		if old_parent_value == tree[parent_index]:
			break
		else:
			cur_index = parent_index

def retrieve(tree, value, index_hash):
	cur_index = 1
	prev_value = -1
	while cur_index<tree.__len__() and tree[cur_index] >= value:
		if 2*cur_index+1<tree.__len__() and tree[2*cur_index] < value and tree[cur_index]==tree[cur_index*2+1]:
			cur_index = 2*cur_index+1
			prev_value = tree[cur_index]
			continue
		prev_value = tree[cur_index]
		cur_index = 2*cur_index

	return index_hash[prev_value]


N,Q = list(map(int, input().split()))
arr = list(map(int, input().split()))

index_hash = {-1:-1}
for i in range(arr.__len__()):
	index_hash[arr[i]] = i+1

tree, offset = create_tree(arr)
while Q>0:
	Q-=1
	x = list(map(int, input().split()))
	if x[0] == 0:
		update(tree, x[1], x[2], offset, index_hash)
	elif x[0] == 1:
		print(retrieve(tree, x[1], index_hash))
	#show_tree(tree[1:], 50)


N,Q=list(map(int,input().split()))
n=list(map(int,input().split()))
tc=Q
while tc:
	tc-=1
	inp=list(map(int,input().split()))
	if inp[0]==1:
		#print 'in if'
		for i in range(N):
			if inp[1]<=n[i]:
				print(i+1)
				break
		else:
			print(-1)

	elif inp[0]==0:
		#print 'in elif'
		n[inp[1]-1]=inp[2]
		#print 'new n:',n
		
	
	


n, q = [int(a) for a in input().split()]
ZA = [int(a) for a in input().split()]

while q > 0:
	ZB = [int(a) for a in input().split()]

	if len(ZB) > 2:
		ZA[ZB[1] - 1] = ZB[2]
	else:
		d = 0
		while d < len(ZA):
			if ZA[d] >= ZB[1]:
				break
			d += 1
		if d < len(ZA):
			print(d + 1)
		else:
			print(-1)
	q -= 1


first_input = list(map(int, input().split()))
N, Q = first_input[0], first_input[1]
given_array = list(map(int, input().split()))

def update_array(input_array, given_array):
	if input_array[1] < len(given_array):
		given_array[input_array[1] - 1] = input_array[2]
		
def find_grater_elem(operation_input, given_array):
	for i, item in enumerate(given_array):
		ind = None
		if item >= operation_input[1]:
			ind = i + 1
			break
	if ind:
		print(ind)
	else:
		print(-1)

for _ in range(Q):
	operation_input = list(map(int, input().split()))
	if len(operation_input) > 2:
		update_array(operation_input, given_array)
	else:
		find_grater_elem(operation_input, given_array)
		


first_input = list(map(int, input().split()))
N, Q = first_input[0], first_input[1]
given_array = list(map(int, input().split()))

def update_array(input_array, given_array):
	if input_array[1] < len(given_array):
		given_array[input_array[1] - 1] = input_array[2]
		
def find_grater_elem(operation_input, given_array):
	for i, item in enumerate(given_array):
		ind = None
		if item >= operation_input[1]:
			ind = i + 1
			break
	if ind:
		print(ind)
	else:
		print(-1)

for _ in range(Q):
	operation_input = list(map(int, input().split()))
	if len(operation_input) > 2:
		update_array(operation_input, given_array)
	else:
		find_grater_elem(operation_input, given_array)
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def build_ta(n, a):
	ta = []
	for idx in range(n):
		elem = (idx+1, arr[idx])
		ta.append(elem)
	ta = sorted(ta, key=lambda e: e[1], reverse=True)
	return ta
	
def ffg(arr, elem):
	ret = -1
	for idx in range(n):
		if arr[idx] >= elem:
			ret = idx + 1
			break
	return ret

def update(arr, idx, elem):
	arr[idx-1] = elem
	return arr
	
n, q = list(map(int, input().strip().split(' ')))
arr = list(map(int,input().strip().split(' ')))
arr = arr[:n]
#ta = build_ta(n, arr)

for idx in range(q):
	arr1 = list(map(int,input().strip().split(' ')))
	if arr1[0] == 1:
		print("%d" %(ffg(arr, arr1[1])))
	else:
		arr = update(arr, arr1[1], arr1[2])
		#ta = build_ta(n, arr)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def fun(A,v):
	for i in range(len(A)):
		if(A[i]>=v):
			return i+1
	return -1

[N,Q]=list(map(int,input().split()))
A=list(map(int,input().split()))
O=[]
for i in range(Q):
	q=list(map(int,input().split()))
	if(q[0]==0):
		A[q[1]-1]=q[2]
	else:
		O.append(fun(A,q[1]))

for i in range(len(O)):
	print(O[i])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math

def retrieve(heap, value):
	indC = 1
	valP = -1
	while indC<heap.__len__() and heap[indC] >= value:
		if 2*indC+1<heap.__len__() and heap[2*indC] < value and heap[indC]==heap[indC*2+1]:
			indC = 2 * indC + 1
			valP = heap[indC]
			continue
		valP = heap[indC]
		indC = 2 * indC

	return valP

def update(tree, ind, value, twoPow, hashedIndexLocations):
	indT = int(ind + twoPow - 1)

	hashedIndexLocations[tree[indT]] = -1
	hashedIndexLocations[value] = ind

	tree[indT] = value
	indC = indT
	while indC>0:
		indP = int(indC/2)
		parentPrev = tree[indP]
		tree[indP] = max(tree[indP*2], tree[indP*2+1])
		if parentPrev == tree[indP]:
			break
		else:
			indC = indP

def treeC(theArray):
	twoPow = math.pow(2, math.ceil(math.log(theArray.__len__(), 2)))
	theArray.extend([-1] * (int(twoPow - theArray.__len__())))

	lC = theArray.__len__()
	#Initialize tree array
	tree= [-1] * lC
	tree.extend(theArray)

	for i in range (lC-1,0,-1):
		if 2*i+1 < tree.__len__()-1:
			tree[i] = max(tree[2*i+1], tree[2*i])
		else:
			tree[i] = tree[2*i]
	return tree, twoPow

def mainworker(N, arr, Q):
	hashedIndexLocations = {-1:-1}
	for i in range(arr.__len__()):
		hashedIndexLocations[arr[i]] = i+1

	heap, twoPow = treeC(arr)
	while Q >0:
		Q -=1
		# print ' query is' , query, 'end' ,
		x = list(map(int, input().split()))
		if x[0] == 0:
			update(heap, x[1], x[2], twoPow, hashedIndexLocations)
		elif x[0] == 1:
			print(hashedIndexLocations[retrieve(heap, x[1])])

N, Q = input().split()
arr = list(map(int, input().split()))

mainworker(N, arr, int(Q))



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
if __name__ == '__main__':
	n,q = list(map(int,input().split()))#n - size of array,q - operations
	a = list(map(int,input().split()))
	for i in range(q):
		op = list(map(int,input().split()))
		if op[0] == 0:
			a[op[1]-1] = op[2]
		elif op[0] == 1:
			found = 0
			for i,item in enumerate(a):
				if item >= op[1]:
					print(i+1)
					found = 1
					break
			if found == 0:
				print(-1)
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
if __name__ == '__main__':
	n,q = list(map(int,input().split()))#n - size of array,q - operations
	a = list(map(int,input().split()))
	for i in range(q):
		op = list(map(int,input().split()))
		if op[0] == 0:
			a[op[1]-1] = op[2]
		elif op[0] == 1:
			found = 0 
			for i,item in enumerate(a):
				if item >= op[1]:
					print(i+1)
					found = 1
					break
			if found == 0:
				print(-1)
	


n,q = [int (i) for i in input().strip().split()]
arr = [int (i) for i in input().split()]
for i in range(q):
	flag = False
	query = [int (i) for i in input().split()]
	if query[0] == 0:
		temp = query[1]-1
		arr[temp] = query[2]
	else:
		temp = query[1]
		for a_i in arr:
			if temp <= a_i:
				print((1+arr.index(a_i)))
				flag = True
				break
				
		if flag == False:
			print ('-1')


arr = list(map(int,input().strip().split()))
arr1 = list(map(int,input().strip().split()))
s= []
for i in range(arr[1]):
	arr2 = list(map(int,input().strip().split()))
	s.append(arr2)
for entry in s:
	if entry[0] == 0:
		arr1[entry[1]-1] = entry[2]
	elif entry[0] == 1:
		try:
			index=next(x[0] for x in enumerate(arr1) if x[1] >= entry[1])
			print(index+1)
		except:
			print(-1)


nq=input().split()
N=int(nq[0])
Q=int(nq[1])

lista=input().split()
lista=[int(x) for x in lista]
lista[1:]=lista
lista[0]=None


for q in range(Q):
	found=False
	query=input().split()
	opcode=int(query[0])

	if not opcode:
		x=int(query[1])
		y=int(query[2])
	
		lista[x]=y
	else:
		v=int(query[1])
		for k in range(1,N+1):
			if v<=lista[k]:		
				print(k)
#				print "ghusa"
				found=True
				break
		if found==False:
			print(-1)
	


(n,q)=list(map(int,input().split()))
l=list(map(int,input().split()))
while q:
	q-=1
	count=0
	arr=list(map(int,input().split()))
	if len(arr)==2:
		for i in range(len(l)):
			# TODO: write code...
			if l[i]>=arr[1]:
				count=1
				print((i+1))
				break
		if count==0:
			print((-1))
			# TODO: write code...
				# TODO: write code...
	elif len(arr)==3:
		l[arr[1]-1]=arr[2]
		continue
		# TODO: write code...


N, Q = input().split(' ')
N = int(N)
Q = int(Q)
input_array = [ int(x) for x in input().strip().split(' ')]
for each in range(0,Q):
	temp = input().strip().split()
	
	if temp[0] == '0':
		x = int(temp[1])
		y = int(temp[2])
		input_array[x-1] = y
	else:
		v = int(temp[1])
		flag = 1
		for n,i in enumerate(input_array):
			if i >= v:
				print(n + 1)
				flag =0
				break
		if flag:
			print(-1)