Ngăn xếp, hàng đợi

Hãy viết một chương trình mô phỏng cách hoạt động của một Ngăn xếp stack. Lần lượt đọc vào các câu lệnh và thực hiện nó. Các câu lệnh mà bạn cần lập trình là:

• init: Khởi tạo một Stack rỗng.
• push: Thêm một số nguyên vào Stack. Số nguyên cần thêm sẽ ở dòng ngay bên dưới câu lệnh này.
• pop: Nếu stack không rỗng, xóa số nguyên ở trên cùng Stack.
• top hoặc peek: Nếu Stack rỗng, in ra \(-1\). Ngược lại, in ra giá trị phần tử ở trên cùng Stack.
• size: In ra số lượng phần tử có trong Stack.
• empty: In ra \(1\) nếu Stack rỗng. Ngược lại, in ra \(0\).

Input

• Dòng đầu tiên chứa số nguyên \(N\), là số câu lệnh. \((1 \leq N \leq 1509)\).
• Dòng thứ hai được đảm bảo chứa câu lệnh init.
• Tiếp theo, sẽ chứa \(N-1\) câu lệnh được mô tả như trên. Với lệnh push sẽ gồm 2 dòng dữ liệu, những lệnh còn lại chỉ gồm 1 dòng dữ liệu.

Số nguyên đằng sau lệnh push có giá trị không âm và bé hơn \(1510\).

Output

• Với mỗi câu lệnh top, peek, size, empty, hãy in ra đáp án trên một dòng riêng biệt.

Sample Tests

Input 1

3
init
push
5
top

Output 1

5

Input 2

18
init
top
peek
push
69
peek
push
96
top
size
pop
size
pop
size
top
pop
push
1
size
init
size

Output 2

-1
-1
69
96
2
1
0
-1
1
0

Sau khi làm bài MyStack 001 xong, bạn cảm thấy Stack thật dễ hiểu nên cũng hơi nhàm chán, bạn muốn chỉnh sửa lại những câu lệnh. Bây giờ, các câu lệnh sẽ là:

• init: Khởi tạo một Stack rỗng.
• push: Thêm một số nguyên vào Stack. Số nguyên cần thêm sẽ ở dòng ngay bên dưới câu lệnh này.
• pop: Nếu stack không rỗng, xóa số nguyên ở trên cùng Stack.
• top: Nếu Stack rỗng, in ra \(-1\). Ngược lại, in ra giá trị phần tử ở trên cùng Stack.
• sum: Tính tổng các phần tử trong Stack và in ra màn hình.

Input

• Dòng đầu tiên chứa số nguyên \(N\), là số câu lệnh. \((1 \leq N \leq 10^5)\).
• Dòng thứ hai được đảm bảo chứa câu lệnh init.
• Tiếp theo, sẽ chứa \(N-1\) các câu lệnh ở sau đó. Với lệnh push sẽ gồm 2 dòng dữ liệu, những lệnh còn lại chỉ gồm 1 dòng dữ liệu.

Số nguyên đằng sau lệnh push có giá trị không âm và bé hơn \(1510\).

Output

• Với mỗi câu lệnh top, sum, hãy in ra đáp án trên một dòng riêng biệt.

Sample Tests

Input 1

8
init
sum
push
9
sum
push
60
sum
pop
sum

Output 1

0
9
69
9

Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. "\(()\)" là dãy ngoặc đúng

2. \(C\) là dãy ngoặc đúng nếu \(C = (A)\) hay \(C = AB\) với \(A, B\) là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: \((), (()), ()(), (())()\)

Ví dụ dãy ngoặc sai: \()(, ((((, ()((, )))), )()(\)

Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài \(n\) (\(n\) chẵn)

Input

• Là số nguyên \(n\) \((n\) chẵn, \(2 \le n \le 30)\)

Output

• In số \(m\) là số lượng các dãy ngoặc đúng có chiều dài \(n\)

Example

4

2

2

1

Một dãy ngoặc đúng là một xâu gồm các ký tự (, ), [, ], { và } định nghĩa như sau:

• Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng,
• Nếu A và B là hai dãy ngoặc đúng thì AB (xâu tạo thành bằng cách lấy xâu A nối vào trước xâu B) cũng là một dãy ngoặc đúng,
• Nếu A là một dãy ngoặc đúng thì (A), [A] và {A} cũng là những dãy ngoặc đúng.

Những xâu không thành lập được theo quy tắc trên không phải là dãy ngoặc đúng.

Ví dụ {[()()[]()]}() là một dãy ngoặc đúng nhưng [(]) và }}}{{{ không phải là những dãy ngoặc đúng.

Input

Vào từ file văn bản PARENTHESES.INP

• Dòng 1 chứa số nguyên dương \(n \leq 10\).
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu có độ dài là số nguyên dương không quá \(10^6\) và chỉ gồm các ký tự (, ), [, ], { và }.

Output

Ghi ra file văn bản PARENTHESES.OUT ứng với mỗi xâu trong file dữ liệu, ghi ra trên một dòng từ YES nếu xâu đó là dãy ngoặc đúng, ghi ra từ NO nếu xâu đó không phải dãy ngoặc đúng.

Example

4
{[()()[]()]}()
[(])
([{}]){[()]}
{{{}}

YES
NO
YES
NO

Nguồn: Thầy Lê Minh Hoàng

Cho một biểu thức hậu tố với số hạng là các số nguyên dương và ba toán tử \(+, -, *\). Hãy tính giá trị của biểu thức hậu tố.

Ví dụ: biểu thức hậu tố: \(2\ 3\ 4\ +\ *\ 5\ -\ 2\ 2\ *\ +\) có giá trị là 13.

Input

• Gồm nhiều dòng thể hiện biểu thức hậu tố, mỗi dòng có một chuối các số hạng là một số nguyên dương trong phạm vi từ \(1\) đến \(100\). Giữa hai số hạng, hoặc giữa hai toán tử, hoặc giữa số hạng và toán tử, cách nhau một khoảng trắng. Chiều dài biểu thức không quá \(100\) ký tự.

Dữ liệu đề bài cho đảm bảo biểu thức hậu tố là hợp lệ. Trong quá trình tính toán đảm bảo trị tuyệt đối các giá trị trung gian không vượt quá \(10^9\).

Output

• Mỗi dòng là giá trị của biểu thức hậu tố tương ứng với dữ liệu vào.

Example

2 3 4 + * 5 - 2 2 * +

13

Hãng cung cấp dịch vụ điện thoại XYZ khuyến khích nhiều người đăng kí thuê bao bằng cách: Khi khách hàng đến đăng kí thuê bao thì sẽ được cấp hai số may mắn là số nguyên dương \(n\) và \(k\), hãng sẽ khuyến mại người đó một số tiền nhận được từ số \(n\) sau khi xóa đúng \(k\) chữ số (\(k\) nhỏ hơn số chữ số của \(n\)). Hải vừa mới đăng kí thuê bao của hãng và được cung cấp hai số \(n\) và \(k\).

Yêu cầu: Bạn hãy giúp Hải xóa đi \(k\) chữ số của số \(n\) để số nhận được số tiền là lớn nhất.

Input

• Dòng thứ nhất là số \(n\) (số chữ số của \(|n| \leq 10^6\))
• Dòng thứ hai là số \(k\ (k < n)\)

Output

• Một dòng duy nhất là số lớn nhất có được sau khi xóa đi \(k\) chữ số của \(n\).

Scoring

• Subtask #1: \(|n| \leq 10^2\).
• Subtask #2: \(|n| \leq 10^4\).
• Subtask #3: \(|n| \leq 10^6\).

Example

58816
2

886

2357111317192329
6

7317192329

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử. Ta định nghĩa mảng \(B\) gồm \(n\) phần tử, với \(B[i]\) được tính như sau:

• Bằng \(A[j]\) là phần tử gần nhất bên trái \(A[i]\) và nhỏ hơn hoặc bằng \(A[i]\) (với \(1\le j<i, j\) lớn nhất có thể, \(A[j] \le A[i]\)).
• Bằng \(0\) khi không tồn tại \(A[j]\) như trên.

Ví dụ: Với \(A = {2,5,3,6}\) thì \(B = {0,2,2,3}\)

1. 
   \(A[1]\) là số đầu tiên trong dãy \(⇒ B[1] = 0\)
2. 
   Số gần nhất bên trái nhỏ hơn hoặc bằng \(5\) là \(2\) \(⇒ B[2] = 2\)
3. 
   Số gần nhất bên trái nhỏ hơn hoặc bằng \(3\) là \(2\) \(⇒ B[3] = 2\)
4. 
   Số gần nhất bên trái nhỏ hơn hoặc bằng \(6\) là \(3\) \(⇒ B[4] = 3\)

Yêu cầu: Cho mảng \(A\), hãy tìm và in ra mảng \(B\) thõa mãn điều kiện trên.

Input

• Dòng đầu tiên là số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên là các phần tử của mảng \(A\).

Output

• Gồm \(n\) số nguyên là các phần tử của mảng \(B\).

Constraints

• \(1\leq n\leq 10^5\)
• \(1\leq A[i]\leq 10^9\)

Scoring

• Subtasks \(1\) (\(33,33\%\) số điểm): \(n \le 10^4\)
• Subtasks \(2\) (\(66,67\%\) số điểm): Không có ràng buộc gì thêm

Example

4
2 5 3 6 

0 2 2 3

Trong giờ học đội ngũ, có \(n\) người xếp hàng dọc đánh số từ \(1\) tới \(n\), người thứ \(i\) có chiều cao là \(h_i\). Người có chỉ số nhỏ hơn đứng trước.

Sau khi xếp hàng, có một số người phàn nàn rằng anh ta bị người khác chắn tầm mắt. Cụ thể là người \(i\) bị người \(j\) chắn tầm mắt nếu:

• Người \(j\) đứng trước người \(i\) \((j < i)\),
• Người \(j\) cao hơn người \(i\) \((h_j > h_i)\),
• Người \(j\) đứng gần người \(i\) nhất (\(j\) lớn nhất có thể).

Yêu cầu: Với mỗi người, cho biết anh ta bị người nào chắn tầm mắt.

Input

Vào từ file văn bản LINEUP.INP

• Dòng 1 chứa số nguyên dương \(n \leq 10^5\).
• Dòng 2 chứa \(n\) số nguyên dương \(h_1, h_2, \ldots, h_n\) cách nhau bởi dấu cách \((\forall i: h_i \leq 10^9)\).

Output

Ghi ra file văn bản LINEUP.OUT \(n\) số \(k_1, k_2, \ldots, k_n\) cách nhau bởi dấu cách. Trong đó \(k_i\) là số hiệu người chắn tầm mắt của người \(i\). Nếu người \(i\) không bị ai chắn tầm mắt, thì quy ước \(k_i = 0\).

Example

9
30 20 10 40 90 50 40 60 70 

0 1 2 0 0 5 6 5 5

Nguồn: Thầy Lê Minh Hoàng