Có $N$ học sinh tại SEATST. Mỗi học sinh đại diện cho đúng một quốc gia. Sau cuộc thi, tất cả các học sinh đều đạt được các số điểm khác nhau.

Prabowo chuẩn bị đăng bảng xếp hạng lên trang web chính thức. Đối với mỗi học sinh, bảng xếp hạng liệt kê quốc gia, số điểm, thứ hạng toàn cầu và thứ hạng trong quốc gia của họ.

• Thứ hạng toàn cầu của một học sinh được định nghĩa là số lượng học sinh có điểm cao hơn họ.
• Thứ hạng trong quốc gia của một học sinh được định nghĩa là số lượng học sinh cùng quốc gia có điểm cao hơn họ.

Một ví dụ về bảng xếp hạng được hiển thị dưới đây:

Lưu ý rằng cả thứ hạng toàn cầu và thứ hạng trong quốc gia đều bắt đầu từ $0$ và không có thứ hạng nào bị bỏ qua (cả trên toàn cầu lẫn trong một quốc gia).

Tuy nhiên, khi bảng xếp hạng được đăng tải trực tuyến, Prabowo đã quên đăng quốc gia và điểm số của các học sinh. Đối với mỗi học sinh, chúng ta chỉ được cung cấp thứ hạng toàn cầu và thứ hạng trong quốc gia của họ.

Prabowo đang cố gắng cứu vãn tình hình và đã giao cho bạn nhiệm vụ giúp họ tính toán hai đại lượng:

• số lượng cặp học sinh khác biệt chắc chắn phải thuộc cùng một quốc gia, VÀ
• số lượng cặp học sinh khác biệt chắc chắn phải thuộc các quốc gia khác nhau.

Cảnh báo: Nếu tồn tại hai cách phân chia học sinh vào các quốc gia thỏa mãn thứ hạng toàn cầu và thứ hạng trong quốc gia, trong đó hai học sinh thuộc cùng một quốc gia ở cách phân chia này nhưng lại thuộc hai quốc gia khác nhau ở cách phân chia kia, thì cặp học sinh này không được tính vào bất kỳ đại lượng nào.

Hãy giúp Prabowo!

Chi tiết cài đặt

Bạn cần cài đặt hai thủ tục sau:

long long count_same_country(int N, std::vector<int> country_rank)
long long count_diff_country(int N, std::vector<int> country_rank)

• $N$: Số lượng học sinh.
• country_rank: Một mảng có độ dài $N$ biểu diễn thứ hạng trong quốc gia. country_rank[i] là thứ hạng trong quốc gia của học sinh có thứ hạng toàn cầu là $i$, với mọi $0 \le i \le N - 1$.

Thủ tục đầu tiên trả về số lượng cặp học sinh khác biệt không có thứ tự sao cho trong tất cả các cách phân chia học sinh vào các quốc gia phù hợp với bảng xếp hạng, các học sinh trong cặp đó đều thuộc cùng một quốc gia.

Thủ tục thứ hai trả về số lượng cặp học sinh khác biệt không có thứ tự sao cho trong tất cả các cách phân chia học sinh vào các quốc gia phù hợp với bảng xếp hạng, các học sinh trong cặp đó không thuộc cùng một quốc gia.

Cả hai thủ tục sẽ được gọi tối đa một lần trong mỗi bộ dữ liệu kiểm tra.

Giới hạn

• $1 \le N \le 1\,000\,000$.
• Tồn tại ít nhất một cách phân chia học sinh vào các quốc gia thỏa mãn country_rank.

Nhiệm vụ con

Đối với 6 nhiệm vụ con đầu tiên, chỉ count_same_country được gọi.

1. ($3$ điểm) $N \leq 8$.
2. ($6$ điểm) country_rank chứa $0$ tối đa hai lần.
3. ($6$ điểm) country_rank không chứa $2$.
4. ($3$ điểm) $N \leq 300$.
5. ($3$ điểm) $N \leq 2000$.
6. ($9$ điểm) Không có giới hạn bổ sung.

Đối với 6 nhiệm vụ con cuối cùng, chỉ count_diff_country được gọi.

1. ($7$ điểm) $N \leq 8$.
2. ($14$ điểm) country_rank chứa $0$ tối đa hai lần.
3. ($14$ điểm) country_rank không chứa $2$.
4. ($7$ điểm) $N \leq 300$.
5. ($7$ điểm) $N \leq 2000$.
6. ($21$ điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

count_same_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

Dữ liệu ra 1

4

Ghi chú

Giả sử học sinh $0$, $1$ và $3$ (đánh chỉ số theo thứ hạng toàn cầu) lần lượt đại diện cho các quốc gia Singapore, Malaysia và Indonesia. Bảng sau liệt kê tất cả các cách có thể tạo ra bảng xếp hạng này:

Có $4$ cặp học sinh luôn thuộc cùng một quốc gia: $(2, 4)$, $(2, 6)$, $(4,6)$ và $(5, 7)$.

Dữ liệu vào 2

count_diff_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

Dữ liệu ra 2

17

Dữ liệu vào 3

count_same_country(5, [0, 1, 0, 1, 2])

Dữ liệu ra 3

2

Dữ liệu vào 4

count_diff_country(5, [0, 1, 0, 1, 2])

Dữ liệu ra 4

4

Trình chấm mẫu

Định dạng dữ liệu vào:

N X

trong đó X là chuỗi same hoặc diff tương ứng với lời gọi hàm count_X_country và C[i] biểu diễn country_rank[i], với mọi $0 \leq i \leq N - 1$.

Định dạng dữ liệu ra:

Một số nguyên duy nhất đại diện cho kết quả của count_X_country.