## Introduction

Finding the first array element exceeding K is not a very difficult task. By just array traversal we can find the required answer. But here we will implement an efficient approach to solve this problem. If we take the brute force approach, it will take O(q*n) time for q such queries. Here we will solve the problem efficiently using a segment tree.

## Problem statement

There is an array of integers. You are given some queries of format** {1,k}** to find the first array element exceeding k (i.e. greater or equal to the value **k)** and some queries of format **{2,i,val}** to update the array element at **ith **index with **val**.

Input

arr[ ] = {2, 4, 7, 8, 6}

Q= { { 1, 5 }, { 2, 3, 5 }, { 1, 4 }, { 1, 8 } }

Output

2

1

-1

Explanation

arr[ ]= {2, 4, 7, 8, 6}

0 1 2 3 4(indices)

So, for the {1,5} query we need to find the index of the first element exceeding 5 i.e. 2 as arr[2]=7.

Updated array after the query { 2, 3, 5 }; arr[ ]= {2, 4, 7, 5, 6}

Similarly, the output of the {1,4} query is 1.

As the updated array doesn’t contain any value exceeding 8, the output of the {1,8} query is -1.

Note: Please try to solve the problem first and then see the below solution approach.

Also see, __Euclid GCD Algorithm__