Cho một chuỗi chỉ gồm các kí tự tương ứng theo ba loại ngoặc: '(', ')', '[', ']', '{', '}'.

Một dãy ngoặc hợp lệ được định nghĩa theo quy tắc đệ quy:

• Chuỗi rỗng "" được coi là là hợp lệ.
• Nếu A là hợp lệ thì (A), [A], {A} cũng hợp lệ.
• Nếu A và B đều hợp lệ thì phép nối AB cũng hợp lệ.

Ví dụ:

• Hợp lệ: "()", "([])", "{[()]}", "()[]{()}"
• Không hợp lệ: "(]", "([)]", "((("

Cho trước một chuỗi ngoặc. Hãy viết chương trình kiểm tra xem nó có phải là một dãy ngoặc hợp lệ hay không.

Input Specification

Gồm một chuỗi ngoặc trên một dòng duy nhất.

Output Specification

In ra kết quả "YES" hoặc "NO" trên một dòng.

Constraints

Chuỗi ngoặc có độ dài không quá \(10^5\) kí tự.

Input Sample

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

Output Sample

YES

Cho một chuỗi ngoặc hợp lệ chỉ gồm ba loại ngoặc: tròn (), vuông [], và nhọn {}.

Giá trị độ sâu lồng nhau tại một vị trí được định nghĩa là số lượng ngoặc mở chưa được đóng khi xét từ đầu chuỗi đến vị trí đó. Với trường hợp chuỗi rỗng, ta quy ước độ sâu bằng 0.

Cho trước một chuỗi ngoặc hợp lệ. Hãy viết chương trình xác định giá trị độ sâu lớn nhất trong chuỗi ngoặc đó.

Input Specification

Gồm một chuỗi ngoặc hợp lệ trên một dòng duy nhất.

Output Specification

In ra kết quả trên một dòng duy nhất.

Constraints

Chuỗi ngoặc có độ dài không quá \(10^5\) kí tự.

Input Sample

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

Output Sample

3

Biểu thức hậu tố (Reverse Polish Notation – RPN) là cách ghi biểu thức mà trong đó toán tử đứng sau các toán hạng.

Ví dụ: biểu thức (2 + 1) * 3 được ghi ở dạng hậu tố là: 2 1 + 3 *

Theo đó, khi biểu diễn dưới dạng này thì ta không cần sử dụng dấu ngoặc và không cần lưu ý về độ ưu tiên của các toán tử.

Trong bài tập này, ta quy ước hiểu toán tử “/” là phép chia lấy phần nguyên(floor division).
Ví dụ: 13 / 5 = 2, -13 / 5 = -3.

Input Specification

• Dòng thứ nhất chứa số nguyên dương \(n\) – số lượng phần tử (token) trong các biểu diễn RPN.
• Dòng thứ hai chứa đúng \(n\) token, ngăn cách nhau bởi dấu khoảng trắng. Mỗi token là một số nguyên (có thể âm) hoặc một trong bốn toán tử: + - * /

Output Specification

In ra một số nguyên duy nhất là giá trị của biểu thức hậu tố.

Constraints

• \(1 \leq n \leq 10^6\)
• Mỗi số nguyên có trị tuyệt đối không vượt quá \(10^9\)
• Biểu thức đảm bảo các phép toán hợp lệ, các giá trị kết quả luôn có giá trị tuyệt đối không vượt quá \(10^6\).

Input Sample

5
2 1 + 3 *

Output Sample

9

Cho một dãy \(n\) số nguyên. Hỏi ta cần xoá đi ít nhất bao nhiêu số hạng để các số còn lại (giữ nguyên thứ tự) tạo thành một dãy số tăng dần (với ít nhất hai số hạng)? Viết chương trình xác định giá trị đó. Nếu không có cách xoá thoả mãn, in ra kết quả là \(-1\).

Input Specification

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương \(n\),
• Dòng thứ hai chứa dãy \(n\) số nguyên, hai số liên tiếp ngăn cách nhau bởi một dấu khoảng trắng.

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(n \leq 10^4\);
• Mỗi phần tử có giá trị tuyệt đối không quá \(10^6\).

Input Sample

5
1 4 3 2 5

Output Sample

2