Ôn luyện vào chuyên Tin #01

Một công ty xây dựng nọ đang lên kế hoạch cho việc sửa chữa một con đường cao tốc có chiều dài là \(n\) kilomet. Con đường này được đánh số từ \(1\) đến \(n+1\) tại những vị trí cách đều nhau đúng \(1\) kilomet, bắt đầu từ vị trí đầu của con đường. Chi phí sửa chữa cho đoạn \(1\) kilomet từ vị trí \(i\) đến \(i+1\) là \(A_i\) với \(1 \le i \le n\).

Một kiến trúc sư người Ý đảm nhiệm vai trò này và đang khảo sát mức độ hư hại cũng như chi phí để sửa chữa con đường này. Do kinh phí thời điểm hiện tại không đủ để thi công một lúc cả con đường. Anh ấy kế hoạch tính toán để chọn ra đoạn đường phù hợp nhất để sửa chữa đầu tiên. Anh ấy khảo sát con đường bằng cách chọn ra một đoạn từ vị trí \(L\) đến vị trí \(R\) trên con đường và tính xem chi phí sửa chữa trung bình trên \(1\) kilomet của đoạn này là bao nhiêu.

Yêu cầu: Cho \(Q\) câu truy vấn \((L, R)\). Hãy tính chi phí sửa chữa trung bình trên \(1\) kilomet của vị trí \(L\) đến vị trí \(R\).

Input

• Dòng đầu tiên gồm số \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
• Dòng thứ ba là số \(Q\) – số lượng câu truy vấn.
• Q dòng tiếp theo, mỗi dòng gồm 2 số \(L\) và \(R (L<R)\).

Output

• Gồm \(Q\) dòng tương ứng là kết quả của câu truy vấn thứ \(i\), kết quả được làm tròn đến chữ số thập phân thứ \(6\).

Scoring

• \(0 \le A_i \le 10^9\)
• Subtask \(1\) (\(70\%\) số điểm): \(1 \le q,n \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le q,n \le 5*10^4\).

Example

5
1 2 3 4 5
3
1 4
2 5
4 6

2.000000
3.000000
4.500000

Một thần bài người Italy đang chơi một trò chơi với những lá bài. Bộ bài gồm \(n\) lá bài được đánh số từ \(1\) đến \(n\). Anh ấy bốc \(k\) lá bài bất kì từ bộ bài và trải dài ra sàn nha. Sau đó, anh ấy muốn thay \(1\) lá bài bất kì trên sàn nhà bằng \(1\) lá bài bất kì trong những lá bài còn lại của bộ bài.

Vị thần bài này muốn tổng của \(k\) lá bài sau khi thay phải lớn nhất có thể. Tuy nhiên anh ấy là thần bài nên không giỏi Toán cho lắm, bạn hãy giúp anh ấy nhé.

Input

• Dòng đầu tiên gồm \(n\) và \(k\) \((k < n)\).
• Dòng tiếp theo gồm \(k\) số nguyên khác nhau \(A_i\) \((1 \leq A_i \leq n)\).

Output

• Gồm 1 dòng duy nhất là tổng số lớn nhất của \(k\) lá bài sau khi đã được thay \(1\) lá.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(2 \leq n \leq 10 ^ 3\).
• Subtask \(2\) (\(30\%\) số điểm): \(2 \leq n \leq 2 * 10 ^ 5\)

Example

5 2
1 3 

8

Có một nhà toán học Italien đang nghiên cứu tính chất của một dãy số. Anh ấy có một dãy số gồm \(n\) số nguyên. Anh ấy bốc ra một lần \(3\) số bất kì trong dãy (không quan trọng thứ tự bốc \(3\) số này) và muốn biết xác suất để \(3\) số vừa bốc là một bộ số ziczac.

Bộ số ziczac là bộ số gồm \(3\) số \((i,j,k)\) sao cho \(A[i]>A[j]<A[k]\) và \(1 \leq i<j<k \leq n.\)

Input

• Dòng đầu tiên là số n.
• Dòng tiếp theo là dãy gồm n số nguyên.

Output

• Gồm một dòng duy nhất là xác suất cần tìm, làm tròn đến chữ số thập phân thứ \(6\).

Constraints

• \(0 \leq A_i \leq 10 ^ 9\)

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(3 \leq n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(3 \leq n \leq 5000\)

Example

4
5 3 1 3 

0.500000

Đại Dương mới học về định nghĩa tam giác cân ở trên trường. Cậu được biết một tam giác cân là 1 tam giác mà có 2 cạnh bằng nhau.

Đại Dương cũng đã học và giải qua bài đếm bộ số tam giác (BOSOTG hay TAMHOP).

Vì vậy, Đại Dương cũng muốn ra 1 bài toán tương tự như vậy. vì lười viết đề, nên bài toán của cậu được tóm tắt như sau:

Cho n số nguyên dương. Hãy đếm số lượng bộ 3 số tam giác cân \(\left(a_i,a_j,a_k\right)\) với \(i<j<k\).

Input:

• Dòng đầu tiên gồm một số \(n\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1\), \(a_2\), \(a_3\),... \(a_n\). \(\left(a_i\leq 10^7\right)\)

Output:

• Gồm một số duy nhất là số lượng bộ ba số tam giác cân khi chia lấy dư cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n\leq 300\)
• Subtask \(2\) (\(20\%\) số điểm): \(n\leq 10000\)
• Subtask \(3\) (\(20\%\) số điểm): \(n\leq 10^5\)
• Subtask \(4\) (\(20\%\) số điểm): \(n\leq 10^6\)
• Subtask \(5\) (\(10\%\) số điểm): \(n\leq 10^7\)

8
5 3 2 9 5 4 9 5

22