Trong một đợt khảo sát để thu nhận thông tin từ phía học sinh, cơ sở kinh doanh ABC có ý định tặng quà cho những học sinh tham gia khảo sát. Nhân viên A dự định mua bánh để tặng cho học sinh. A nhận thấy là cần mua tối thiểu n chiếc bánh để tặng cho học sinh. Tại cửa hàng bán bánh, biết đơn giá mỗi chiếc bánh là m đồng. Nếu mua từ k chiếc bánh trở lên thì được giảm giá 20% (Có thể mua được nhiều hơn n chiếc bánh mà chi phí ít tiền hơn).

Cho biết n - số bánh A cần mua tối thiểu, m - giá của một chiếc bánh và k – số lượng bánh được áp giảm giá. Hãy xác định số tiền tối thiểu A cần dùng mua bánh để tặng học sinh?

Input

• Gồm một dòng duy nhất có ba số nguyên n, m và k (\(1 \leq n \leq 100; 1 \leq m \leq 10000; 1 \leq k \leq 100\)).

Output

• Gồm một số nguyên là kết quả tìm được theo yêu cầu (nếu kết quả không là số nguyên thì chỉ giữ lại phần nguyên).

Example

10 1000 5

8000

Trong một đợt khảo sát, cơ sở kinh doanh ABC có ý định tặng quà cho những học sinh tham gia. Nhân viên B có phát ra các phiếu khảo sát gắn số hiệu. Do kinh phí tặng quà có hạn nên B chỉ lựa chọn tặng quà cho những học sinh có phiếu với số hiệu là số chính phương lẻ. (Số chính phương là số bằng bình phương đúng của một số nguyên; ví dụ: số 4 và số 9 là số chính phương, số 9 là số chính phương lẻ).

Cho số tự nhiên n. Hãy xác định số lượng các số chính phương lẻ trong khoảng từ 1 đến n và tổng của chúng?

Input

• Gồm một dòng duy nhất chứa số nguyên n (\(0 < n < 3 * 10^{9}\)).

Output

• Dòng đầu tiên chứa một số là số lượng các số chính phương lẻ.
• Dòng thứ hai chứa một số là tổng của các số chính phương lẻ theo yêu cầu.

Example

9

2
10

Trong một đợt khảo sát thu nhận thông tin từ khách hàng của cơ sở kinh doanh ABC, nhân viên B có phát ra n phiếu (các phiếu được ghi số hiệu không trùng nhau). Sau khảo sát nhận về đủ n phiếu đó nhưng số hiệu các phiếu có thể chưa đúng thứ tự tăng. B làm theo các đợt lựa chọn các phiếu để xếp lại thứ tự. Mỗi đợt lựa chọn thực hiện: mở phiếu nhận về từ đầu đến cuối, chọn phiếu số hiệu phù hợp tiếp theo.

Ví dụ: có 5 phiếu nhận về có thứ tự số hiệu: 3, 1, 4, 2 và 5. Đợt 1 chọn phiếu có số hiệu 1 và 2; đợt 2 chọn phiếu có số hiệu 3, 4 và 5. (đầu tiên phải chọn phiếu số hiệu 1, tiếp theo là phiếu số hiệu 2...; nếu cần k đợt thì phiếu số hiệu n chọn cuối cùng của đợt k).

Cho biết số hiệu của n phiếu nhận về. Hãy xác định số đợt lựa chọn ít nhất nhân viên cần thực hiện để nhận được các phiếu có số hiệu theo thứ tự tăng?

Input

• Dòng đầu tiên chứa số nguyên dương n (\(1 < n \leq 10^{7}\)) là số lượng phiếu.
• Dòng thứ hai chứa n số nguyên dương, số thứ \(i\) là \(a_i\) - số hiệu của phiếu số \(i\) (\(a_i \leq n\)).

Output

• Gồm một dòng duy nhất là kết quả tìm được theo yêu cầu.

Example

5
3 1 4 2 5

2

Cơ sở kinh doanh ABC nhận về n phiếu của đợt khảo sát. Nhân viên T cần phân tích dữ liệu dựa vào các phiếu khảo sát đó. Mỗi phiếu đã được tính điểm và ghi nhận lại theo cách của T. Điểm của phiếu số \(i\) là \(a_i\) (với \(i \neq j\) thì \(a_i \leq a_j\)). Nếu 3 phiếu số \(i, j\) và \(k\) thỏa mãn điều kiện: \(a_i + a_j = 2 * a_k\) (với \(i \neq j, j \neq k\) và \(i \neq k\)) thì 3 phiếu đó có tính chất TB. T cần xác định số cặp phiếu có tính chất TB.

Cho biết điểm của n phiếu. Hỏi có bao nhiêu cặp 3 phiếu có tính chất TB?

Input

• Dòng đầu tiên chứa số nguyên dương n (\(2 < n \leq 10^{4}\)) là số lượng phiếu.
• Dòng thứ hai chứa n số nguyên dương, số thứ \(i\) là \(a_i\) - số hiệu của phiếu số \(i\) (\(|a_i| \leq 10^6\)).

Output

• Gồm một dòng duy nhất là kết quả tìm được theo yêu cầu.

Example

5
2 3 1 5 6

2

Cơ sở kinh doanh ABC nhận về n phiếu của đợt khảo sát. Nhân viên TZ cần phân tích dữ liệu dựa vào các phiếu khảo sát đó. Mỗi phiếu đã được TZ tính điểm và ghi nhận thành dãy số A. Dãy \(A\) có n số nguyên, điểm của phiếu số \(i\) là \(a_i\).

Gọi dãy \(B\) là dãy con của \(A\) có tính chất TBZ nếu thỏa mãn cả ba điều kiện:

• Điều kiện 1: \(k\) là số phần tử thuộc B thì \(k\) phải lớn hơn 1.
• Điều kiện 2: Tồn tại giá trị \(i\) (\(0 < i \leq n-k+1\)) sao cho: \(a_i=b_1; a_i+1=b_2; …; a_i+k-1=b_k\).
• Điều kiện 3: Tổng các phần tử của \(B\) bằng 0.

TZ cần xác định số dãy con của \(A\) có tính chất TBZ.

Cho biết thông tin của dãy \(A\). Hỏi \(A\) có bao nhiêu dãy con có tính chất TBZ?

Input

• Dòng đầu tiên chứa số nguyên dương n (\(1 < n \leq 10^{7}\)) là số lượng phiếu.
• Dòng thứ hai chứa n số nguyên dương, số thứ \(i\) là \(a_i\) - số hiệu của phiếu số \(i\) (\(|a_i| \leq 10^9\)).

Output

• Gồm một dòng duy nhất là kết quả tìm được theo yêu cầu.

Example

5
2 -3 1 5 -6

2