2B. 국립 스택 (National Stack)

문제

인덱스국 종교사 : Day 2

인덱스국은 하나의 거대한 국립 스택을 가지고 있습니다. 이 스택은 국력을 과시하기 위한 스택으로, 왕이 매일 정수 하나를 넣는 관례가 있습니다 . 수를 넣을 때 국립 스택이 만족해야 할 조건이 하나 있는데, 스택에 넣을 수는 스택의 top보다 크거나 같아야 한다는 것입니다. 그래서 인덱스국의 노예들은 왕이 X를 넣기 전에 스택에서 X보다 큰 수들을 모두 빼냅니다.

이 스택의 중요한 역할은 국민들의 운세를 보는 용도로 사용된다는 것입니다. 운세를 보고 싶은 국민들은 당신에게 다음과 같은 질문을 던집니다.

'T일의 스택에서 X보다 큰 원소들 중에 가장 작은 원소는 뭐였나요?'

당신은 인덱스국 국민 전원의 질문에 일일이 대답하기에는 너무 힘들었기 때문에, 그들의 질문에 자동으로 대답하는 프로그램을 만드려고 합니다. 단, 스택에 아무것도 없는 스택 완공일은 0일로 취급됩니다.

구현 세부 사항

다음 함수들을 구현하세요.

void init()

이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
이 함수는 0일에 호출됩니다.

void add(int64 X)

이 함수는 스택에 정수 X를 넣을 때 호출됩니다.
이 함수가 호출되면 하루가 지난 후 X가 스택에 삽입됩니다.

int64 getUpperBound(int T, int64 X)

이 함수는 오늘의 운세를 질문받았을 때 호출됩니다.
이 함수는 T일의 스택에서 X보다 큰 원소 중 가장 작은 원소의 값을 반환해야 합니다. 단, 답이 존재하지 않을 경우 −1을 반환해야 합니다.
이 함수가 호출되기 전에 add 함수가 T회 이상 호출되었음이 보장됩니다.
add 함수와 getUpperBound 함수는 합쳐서 Q번 호출됩니다.

제한 조건

1 ≤ Q ≤ 2,000,000
0 ≤ X ≤ $10^{18}$

서브태스크

서브태스크	점수	`Q`	`X`
1	2	`Q` ≤ 2,000	`X` ≤ $10^{18}$
2	8	`Q` ≤ 2,000,000	`X` ≤ 1,000
3	5	`Q` ≤ 2,000,000	`X` ≤ $10^{18}$

예제 입출력

그레이더는 다음 함수를 호출합니다.

init()

그레이더는 add 함수를 호출합니다.

add(10)

add(20)

add(15)

add(1)

스택의 상태는 다음과 같습니다.

0일 : []
1일 : [10]
2일 : [10, 20]
3일 : [10, 15]
4일 : [1]

그레이더는 getUpperBound 함수를 호출합니다.

getUpperBound(2, 12) = 20

getUpperBound(3, 12) = 15

getUpperBound(4, 12) = −1

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

line 1 : Q
line i (2 ≤ i ≤ Q) : 1 X (add(X)) or 2 T X (getUpperBound(T, X))