Ngăn xếp - Hàng đợi (hai đầu) - remake

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

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

Một dấu ngoặc bao gồm những ký tự như sau: (, ), {, }, [, or ].

Một cặp ngoặc đúng bao gồm (), {}, []. Còn lại, những cặp ngoặc như ((, (}, [},... đều không phải là cặp ngoặc đúng.

Ta định nghĩa một chuỗi ngoặc đúng như sau:

1. Là một chuỗi rỗng.
2. Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm ở giữa một cặp ngoặc đúng. (VD: "[{}]" là đúng thì "(+[{}]+)" sẽ đúng).
3. Hoặc, là chuỗi bao gồm một chuỗi ngoặc đúng nằm bên cạnh một chuỗi ngoặc đúng. (VD: "{[]}" là đúng thì "{[]}+[()]" sẽ đúng).

Đề bài cho bạn \(N\) chuỗi ngoặc. Nếu chuỗi thứ \(i\) là chuỗi ngoặc đúng, in ra YES, ngược lại in ra NO.

Input

• Dòng đầu tiên chứa số nguyên \(N\) là số truy vấn \((1 \leq N \leq 1000)\)
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi ký tự \(S_i\), chỉ bao gồm các dấu ngoặc. $(1 \leq $ Độ dài \(S_i \leq 1000)\)

Output

• \(N\) dòng, dòng thứ \(i\) in ra YES hoặc NO tương ứng với nếu chuỗi \(S_i\) là chuỗi ngoặc đúng hoặc không đúng.

Example

3
{[()]}
{[(])}
{{[[(())]]}}

YES
NO
YES

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

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