Mirko je posjetio svoju najdražu trgovinu, te na izlasku vidio da su rum pločice na sniženju, ni pet ni šest (a ni ostali prirodni brojevi) kupio ih je \(N\). Došavši kući, sve ih je poslagao na stol redom, no shvatio da nisu sve iste, te je svaka okusa \(a_i\) (svi su različiti).

Sada svako jutro kada pali svoje računalo traži okus koji mu se taj dan najviše sviđa, no ukoliko ga nema, traži onaj njemu lijevo ili desno (ovisno na koju nogu je ustao iz kreveta taj dan) te ukoliko lijevo/desno nema susjeda, tada gleda s druge strane kružno.

Pomozite mu odgovarajući na \(Q\) upita za svaki dan.

Ulazni podatci

U prvom redu nalazi se cijeli broj \(N\) \((1 \leq N \leq 200000)\)

U drugom redu nalazi se \(N\) brojeva \(a_i\) odvojenih razmakom. \((a_i <= 1e9)\)

U trećem redu nalazi se broj \(Q\) \((1 \leq Q \leq 200000)\)

U idućih \(Q\) redaka nalazi se par \(q_i\) i \(lr_i\), gdje je \(q_i\) cijeli broj koji predstavlja mjesto upita a \(lr_i\) slovo 'L' ili 'R' ovisno koja je strana upita.

Izlazni podatci

Ispišite \(Q\) brojeva koji predstavljaju rezultate upita, svaki u novoj liniji.

Podzadatci

Ulaz primjera 1

3
2 3 1
2
1 L
1 R

Izlaz primjera 1

1
2

Ulaz primjera 2

5
3 2 1 5 4
3
2 L
1 L
2 R

Izlaz primjera 2

2
1
5