Đề thi thử Học sinh giỏi THCS (VTT, contest 1)

Trong giờ học vẽ, cô giáo đã chuẩn bị cho các cháu mẫu giáo một tờ giấy vẽ lên đó \(n\) đường thẳng bằng bút chì, đường thẳng thứ \(i\) có độ dài là \(a_{i}\).

Cô giáo yêu cầu các bé trong lớp cần làm cho các đoạn thẳng bằng nhau, để làm việc đó các bé phải dùng bút chì vẽ thêm vào các đoạn thẳng làm chúng dài thêm, hoặc có thể dùng tẩy để xóa đi độ dài các đoạn thẳng làm chúng ngắn lại. Thời gian để thực hiện thay đổi một đoạn thẳng bằng độ chênh lệch chiều dài giữa đoạn thẳng cũ với đoạn thẳng mới được tạo ra.

Yêu cầu: Em hãy giúp các bé tạo ra \(n\) đoạn thẳng bằng nhau với tổng chi phí thời gian nhỏ nhất.

Input

• Dòng đầu chứa một số nguyên dương duy nhất \(n\) \((1 \leq n \leq 2 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• In ra một số nguyên là tổng chi phí thời gian nhỏ nhất.

Example

5
2 3 1 5 2

5

Cho dãy gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\).

Bạn phải trả lời \(n\) truy vấn, mỗi truy vấn cho một số nguyên \(k\), bạn phải đếm số lượng vị trí \(x < k\) sao cho \(a_{x} = a_{k}\) và số lượng vị trí \(y > k\) sao cho \(a_{y} = a_{k}\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) \((1 \leq n, q \leq 10^{6})\) lần lượt là độ dài dãy và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\) là dãy \(a\).
• \(q\) dòng tiếp theo, dòng thứ \(i\) chứa duy nhất một số nguyên dương \(k_{i}\) \((1 \leq k_{i} \leq n)\) biểu diễn truy vấn thứ \(i\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa hai số nguyên là số lượng vị trí \(x\) và số lượng vị trí \(y\) thỏa mãn thể hiện câu trả lời cho mỗi truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_{i} \leq 10^{6}\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

10 4
2 1 3 2 2 5 4 2 3 5
1 
7
4
10

0 3
0 0
1 2
1 0

Mr Been đang cố gắng gõ một chuỗi ngoặc đơn cân bằng vào máy tính xách tay, nhưng anh ta rất vụng về nên anh ta hay gõ mất các kí tự. Hãy giúp anh ta tính xem có bao nhiêu kí tự trong chuỗi ngoặc đơn cần phải được đổi chiều (có nghĩa là đổi dấu mở ngoặc đơn thành dấu đóng ngoặc đơn, và ngược lại) để chuỗi ban đầu thành chuỗi cân bằng.

Có nhiều cách để định nghĩa một chuỗi ngoặc là “cân bằng.” Cách dễ nhất là số lượng dấu mở ngoặc ( bằng số lượng dấu đóng ngoặc ) và với bất kì chuỗi tiền tố nào, số lượng dấu mở ngoặc đơn ( phải lớn hơn hoặc bằng số lượng dấu đóng ngoặc đơn ). Trong những ví dụ sau đây, những chuỗi ở bên dưới là chuỗi cân bằng:

()
(())
()(()())

Những chuỗi sau đây là chuỗi không cân bằng:

)(
())(
((())))

Input

• Một chuỗi dấu ngoặc đơn có độ dài tối đa là 100.000 kí tự.

Output

• Một số tự nhiên duy nhất là số lượng dấu ngoặc đơn nhỏ nhất cần phải được đổi chiều để biến chuỗi ban đầu thành chuỗi cân bằng.

Example

())(

2

Cho một bảng chữ số gồm \(n \times n\) ô vuông và một số nguyên dương \(k\). Tại một ô giao nhau giữa hai hàng \(i\) \((1 \leq i \leq n)\) và cột \(j\) \((1 \leq j \leq n)\) có giá trị \(i \times j\).

Ví dụ: \(n = 5\), ta có bảng số như sau:

Yêu cầu: hãy lập trình tìm số lần xuất hiện của \(k\) trong bảng số trên.

Input

• Một số duy nhất chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq n \leq 10^{6}, 1 \leq k \leq 10^{12})\).

Output

• Ghi ra một số nguyên là kết quả tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n, k \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

5 3

2