Tornade

Fenomenele sunt neobservabilul devenit observabil. - Anaxagoras, Atena, circa 500 BC
Multe dezastre naturale sunt pe acest pământ, dar dintre toate, tornadele sunt cele mai dezastruoase. - Marele Oracol Axel, Memphis, circa 2560 BC

Se știe că egiptenii antici erau speriați de tornadele care le devastau periodic pământul și le distrugeau piramidele. Prin urmare, odată cu începerea lucrărilor la Marea Piramidă din Giza, populația a devenit din ce în ce mai neliniștită la gândul că zeii se vor mânia pe îndrăzneala oamenilor de a se apropia de cer și vor trimite o tornadă cum nu s-a mai văzut să le distrugă munca.

În încercarea de a-i liniști, preotul local a apelat la ajutorul Marelui Oracol Axel care, bând din poțiunea zeilor, posedă puterea de a intra într-o transă profundă și de a vorbi cu aceștia. După multe zile și nopți de negocieri și dezbateri aprige care puteau fi provocate, dar și reparate doar cu ajutorul acelui nectar magic, Oracolul Axel s-a întors la egipteni cu un plan de construcție care să aibă aprobarea Comisiei Divine pentru Construcții Pământești.

O piramidă este formată din $N$ straturi orizontale de blocuri de piatră astfel încât primul strat conține $N$ blocuri, al doilea conține $N - 1$ și tot așa până la al $N$-lea strat care conține un singur bloc (vezi desenul). Fiecare bloc de piatră are o anumită rezistență calculată în funcție de o multitudine de factori (tipul materialului, densitate etc.) și exprimată printr-un număr natural.

Întrucât primul strat al piramidei fusese deja construit, acesta va rămâne așa cum este. Fiecare dintre următoarele $N - 1$ straturi va fi de tip min sau max și blocurile vor fi așezate după cum urmează:

• Pentru un strat de tip min, fiecare bloc de piatră trebuie să aibă rezistența egală cu minimul dintre rezistențele celor două blocuri de piatră peste care este așezat.
• Pentru un strat de tip max, fiecare bloc de piatră trebuie să aibă rezistența egală cu maximul dintre rezistențele celor două blocuri de piatră peste care este așezat.

De exemplu dacă stratul de jos al piramidei este format din blocuri cu rezistențele $1, 3, 4, 6, 5, 1, 3$ în această ordine și nivelele care urmează trebuie să fie de tipurile: $\{\min, \max, \max, \min, \max, \min\}$, atunci piramida va arăta ca în desenul de mai jos.

În semn de mulțumire pentru ajutorul oferit, egiptenii au decis să îi ridice Oracolului Axel o statuie pe care să o așeze chiar în vârful piramidei, însă pentru ca această să nu distrugă integritatea structurală a acestei construcții grandioase, ei au nevoie să știe care va fi rezistența blocului de piatră aflat pe nivelul cel mai de sus.

Cerință

Dându-se structura primului strat al piramidei și tipul fiecăruia dintre cele $N - 1$ straturi care trebuie construite, determinați care va fi rezistența blocului de piatră din vârf.

Date de intrare

Pe prima linie a fișierului de intrare tornade.in se află un număr $N$, numărul de straturi din care va fi formată piramida.

Pe a doua linie se află $N$ numere pozitive, $r_1, r_2 \ldots r_N$, reprezentând rezistențele blocurilor de piatră care formează primul strat.

Pe a treia linie se află un șir $T$ format din $N - 1$ caractere din mulțimea $\{M, m\}$ care descrie tipul nivelelor care mai trebuie construite, de jos în sus. Caracterul $M$ indică faptul ca nivelul este de tip max, iar caracterul $m$, de tip min.

Date de ieșire

În fișierul de ieșire tornade.out se va afișa un singur număr reprezentând rezistența blocului de pe nivelul al $N$-lea.

Restricții și precizări

• $2 \leq N \leq 1 \ 000 \ 000$
• $1 \leq r_i \leq N$

Exemplul 1

tornade.in

7
1 3 4 6 5 1 3
mMMmMm

tornade.out

5

Explicație

Exemplul corespunde desenului din enunț.

Exemplul 2

tornade.in

7
4 5 3 6 5 1 3
mMMmMm

tornade.out

5

Exemplul 3

tornade.in

2
1 2
M

tornade.out

2