Mirko's average

To add up several numbers you usually add the first two, then add the third number to that result, then add the fourth number to the new result, and so on. Mirko decided that an average can be computed the same way. He first takes the average of the first two numbers, then the average of that result and the third number, then the average of the new result and the fourth number, continuing to the last number.

For the sequence 1, 5, 9, 7 Mirko computes (1 + 5) / 2 = 3, then (3 + 9) / 2 = 6, and finally (6 + 7) / 2 = 6.5. The real average of this sequence is 5.5, not 6.5.

Mirko recently finished every episode of Dexter and True Detective, so he has nothing left to do and plays with averages instead. Now and then he changes two elements of his sequence and tries to guess whether the average produced by his own method went down, went up, or stayed the same. Help Mirko and write a program that answers these questions.

The first line contains the length of the sequence $N$ ($2 \le N \le 100\,000$).

The second line contains the $N$ integers of Mirko's sequence. Each integer is between $1$ and $10^9$.

The third line contains the number of changes $M$ ($1 \le M \le 100\,000$).

Each of the next $M$ lines holds one change in the form p A q B. It means: set the $p$-th element of the sequence to $A$ and the $q$-th element to $B$. Here $1 \le p, q \le N$, $p \ne q$, and $1 \le A, B \le 10^9$. The changes are cumulative, so the changed sequence is the one the next change applies to.

For each change print one line: < if the average produced by Mirko's method went down, > if it went up, and = if it stayed the same.

In the first example the sequence and Mirko's average take these values in order.