Joseph developed a device that allows people to decrease or increase their height by at most $$$D$$$ units. He's playing with his friend Lucas on a circuit with N houses, numbered from $$$1$$$ to $$$N$$$, on which Lucas can only get inside if his height is exactly equal to the height of the door of the house he's trying to get in. There will be two types of queries:
1. There will be given two integers $$$i$$$ and $$$X$$$, meaning that the i-th house's height is now equal to $$$X$$$;
2. There will be given two integers $$$L$$$ and $$$D$$$, meaning that Joseph's device can only increase or decrease someone's height by at most $$$D$$$ units, and that Lucas will walk sequentially through the circuit, starting with height equal to $$$A[L]$$$, on the $$$L$$$-th house, until he finishes the circuit or encounters a house where he can't get in. For each query of this type, you must answer on which house he will stop. Note that Lucas can only go to house $$$i+1$$$ from the house $$$i$$$ if $$$|A[i + 1] - A[i]| \leq D$$$.
The first line contains one integer $$$N$$$ $$$(1 \leq N \leq 2*10^5)$$$, representing the number of houses on the circuit. The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \leq A_i \leq 2*10^5)$$$, where $$$A_i$$$ is the height of the door of the $$$i$$$-th house. The third line contains a single integer $$$Q$$$ $$$(1 \leq Q \leq 2*10^5)$$$, the number of queries. Then, $$$Q$$$ lines follow, each of them containing three integers: $$$t_i$$$ $$$(1 \leq t_i \leq 2)$$$, $$$a_i$$$ and $$$b_i$$$ $$$(1 \leq a_i \leq N, \ 1 \leq b_i \leq 2*10^5)$$$. $$$t_i$$$ stands for the type of $$$i$$$-th query, and $$$a_i$$$ and $$$b_i$$$ are the $$$i$$$-th query's parameters, according to the description on the problem's statement.
For each query of the second type, output one line containing a single integer, representing the number of the house where Lucas will finish his walk.
5 1 3 5 7 9 5 2 1 2 2 1 1 1 5 100 2 1 2 2 1 100
5 1 4 5
| UFPE Starters Final Try-Outs 2019 |
|---|
| Finished |
