Trung vị của một dãy số nguyên \(a_1, a_2, \dots, a_n\) được sắp xếp tăng dần là \(a_{\lfloor \frac{n+1}{2} \rfloor}\), với \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\). Nếu dãy \(a\) chưa được sắp xếp tăng dần, ta sắp xếp lại dãy rồi tìm trung vị.

Một dãy \(b_1, b_2, \dots, b_n\) được gọi là hoán vị của một dãy \(a_1, a_2, \dots, a_n\) khi và chỉ khi tồn tại một cách sắp xếp các phần tử của dãy sao cho thu được dãy \(b\).

Yêu cầu

Cho một hoán vị \(a_1, a_2, \dots, a_n\) của dãy \(1, 2, 3, \dots, n\). Với mỗi số nguyên \(v\) (\(1 \le v \le n\)), hãy đếm số đoạn con liên tiếp của dãy nhận \(v\) làm trung vị, hay nói cách khác, hãy đếm số lượng cặp số \((l, r)\) sao cho \(1 \le l \le r \le n\) và \(v\) là trung vị của \(a_l, a_{l+1}, \dots, a_r\).

Input

• Dữ liệu nhập vào từ file 24TFL1C.inp:
  • Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \le n \le 5000\)).
  • Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)).
  • Dữ liệu đầu vào đảm bảo các giá trị đôi một phân biệt.

Output

• Ghi ra file 24TFL1C.out:
  • Gồm \(n\) số nguyên trên cùng một dòng, số nguyên dương thứ \(v\) là số cặp \((l, r)\) sao cho \(a_l, a_{l+1}, \dots, a_r\) nhận \(v\) làm trung vị.

Ràng buộc bổ sung

• \(8\%\) số điểm có \(n \le 9\).
• \(8\%\) số điểm khác có \(n \le 60\).
• \(12\%\) số điểm khác có \(n \le 100\).
• \(12\%\) số điểm khác có \(n \le 300\).
• \(16\%\) số điểm khác có \(n \le 500\).
• \(20\%\) số điểm khác có \(n \le 2000\).
• \(24\%\) số điểm còn lại không có giới hạn gì thêm.

Example

5
1 2 3 4 5

2 4 5 3 1

4
4 2 3 1

1 5 2 2