Insemove

시간 제한1초메모리 제한1024 MB

요약

N개의 삽입과 앞에서 꺼내기 명령이 주어질 때, 각 삽입을 앞이나 뒤에 넣을지 정해 꺼내는 값의 합을 최대로 만드는 문제입니다.

난이도: 보통10점 중 6점
유형: 그리디, 큐, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

Dokoni programeri Tresni i Evomer od zabave kreiraju i razgrađuju niz brojeva. U početku bijaše prazan niz. Tresni Evomeru izdaje naredbe oblika:

“ubaci broj $X$ u niz brojeva”;
“izbaci broj iz niza brojeva”.

Evomer, kada čuje naredbu za ubacivanje, broj $X$ može ubaciti na početak ili na kraj niza, a kada čuje naredbu za izbacivanje, onda mora izbaciti broj koji je na početku niza.

Naredbe za izbacivanje mogu doći samo kada niz nije prazan.

Cilj ovog neobičnog ubijanja dosade je maksimizirati sumu izbačenih brojeva. Zabavi se i ti!

입력

U prvom retku je prirodan broj $N$ ( $2 ≤ N ≤ 200\\,000$ ), broj izdanih naredbi.

U sljedećih $N$ redaka su naredbe redom kojim ih je Tresni izdavao Evomeru. Naredba ubacivanja je oblika UBACI $X$ ( $1 ≤ X ≤ 100\\,000$ ), a naredba izbacivanja je oblika IZBACI.

Uvijek će postojati barem jedna naredba izbacivanja.

출력

U prvi redak ispiši najveću moguću sumu izbačenih brojeva iz teksta zadatka.

U drugi redak ispiši riječ sastavljenu od slova ‘P’ i ‘K’, koji predstavljaju pozicije na koje je Evomer redom ubacivao brojeve u niz. ‘P’ znači da je Evomer broj ubacio na početak, a ‘K’ na kraj niza.

Ako postoji više mogućih rješenja, ispiši bilo koje.

예제3

예제 1
입력
```
3
UBACI 5
UBACI 6
IZBACI
```
예상 출력
```
6
PP
```
예제 2
입력
```
3
UBACI 6
UBACI 5
IZBACI
```
예상 출력
```
6
PK
```

예제 3

입력

5
UBACI 6
UBACI 5
UBACI 7
IZBACI
IZBACI

예상 출력

13
PKP