H. Wanna win? Solve
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdulghafour is a player who loves football. His friend Abo Al-Jood does too.

Every time they play, each one is on a different team. And of course, the team that Abo Al-Jood plays on always loses. But this time, Abdulghafour gave Abo Al-Jood a condition. He told him he must solve a task if he wants to be on the same team and win.

Help Abo Al-Jood solve the task so he can play on the winning team.

You are given an array $$$A$$$ of $$$N$$$ integers. Also, you are given $$$Q$$$ queries, there are two types of queries:

  1. Update Query: '$$$1$$$ $$$i$$$ $$$val$$$' Update the element at position $$$i$$$ to $$$val$$$; $$$A_i \gets$$$ $$$val$$$.
  2. Find Query: '$$$2$$$ $$$i$$$' Find any position $$$j$$$ in the array such that $$$|(i - j)^3| \ge A_j$$$

For a find query, If such a position $$$j$$$ exists, print any valid $$$j$$$. If no such position exists, print -1.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the length of the array.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 10^9$$$) — the elements of the array.

The third line contains an integer $$$Q$$$ ($$$1 \le Q \le 10^5$$$) — the number of queries.

Each of the next $$$Q$$$ lines contains a query in one of the following forms:

  • $$$1$$$ $$$i$$$ $$$val$$$ ($$$1 \le i \le N$$$, $$$1 \le val \le 10^9$$$) — an Update Query.
  • $$$2$$$ $$$i$$$ ($$$1 \le i \le N$$$) — a Find Query.
Output

For each query of type $$$2$$$, output any valid index $$$j$$$ that satisfies the condition, or -1 if no such index exists.

Example
Input
6
1000000 10 100000 10000000 4 5
7
2 1
2 2
2 4
1 6 9
2 4
2 3
2 6
Output
5
5
6
-1
5
2