Bài tập

Trong tiết sinh hoạt lớp, giáo viên chủ nhiệm tổ chức hoạt động phát quà cho các bạn học sinh trong lớp chuyên. Giáo viên phát quà cho học sinh theo quy tắc sau:

• Mỗi học sinh sẽ đem theo một số lượng viên kẹo tùy ý.
• Học sinh xếp thành hàng ngang theo chiều tăng dần (từ trái qua phải) của số kẹo mà mình có.
• Học sinh nào đứng ở vị trí có số thứ tự trùng với số viên kẹo mình đem theo thì sẽ được ưu tiên phát quà trước, tiếp theo giáo viên sẽ phát quà cho các bạn còn lại.

Biết rằng có \(N\) học sinh, học sinh thứ \(i\) đem theo \(a_i\) viên kẹo.

Yêu cầu. Hãy đếm xem có bao nhiêu học sinh được ưu tiên phát quà trước.

\InputFile

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^6)\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((1 \le a_i \le 10^9)\).

\OutputFile

• In ra một số nguyên là số lượng học sinh được ưu tiên phát quà trước.

\Examples
\beginexample
\exmp
5
3 3 4 3 6

2

\exmp
5
5 3 4 7 6

0

\endexample

\Note
Ở ví dụ thứ nhất, sau khi sắp xếp dãy tăng dần ta được \(3, 3, 3, 4, 6\). Hai học sinh ở vị trí \(3\) (có \(3\) kẹo) và vị trí \(4\) (có \(4\) kẹo) được ưu tiên phát quà.

\Scoring

• (50%) \(N \le 10^3\);
• (50%) Không có ràng buộc thêm.

\endproblem

Cho một ma trận số nguyên \(m \times n\).

Bạn phải trả lời \(q\) truy vấn, mỗi truy vấn trả lời tổng các phần tử cùng hàng và cùng cột với phần tử \((u,v)\)

Input

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\) \((m ,n \le 5.10^3)\)

• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương \((a_{i,j} \le 10^9)\)

• Dòng tiếp theo chứa số nguyên dương \(q\) \((q \le 10^6)\) - số truy vấn.

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) - là tọa độ của phần tử cần trả lời.

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Example

3 3
4 6 7
1 3 4
2 4 6
2
1 3
2 2

27
18

Cho dãy số nguyên \(a\) gồm \(N\) phần tử. Nhiệm vụ của bạn là xử lý \(Q\) truy vấn trên dãy, mỗi truy vấn thuộc một trong ba loại sau:

• 2 u v --- In ra tổng các bình phương phần tử trong đoạn \([u, v]\).
• 1 u v x --- Cộng thêm \(x\) vào tất cả các phần tử trong đoạn \([u, v]\).
• 0 u v x --- Gán tất cả các phần tử trong đoạn \([u, v]\) bằng \(x\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) \((1 \leq N, Q \leq 10^5)\) --- số phần tử của 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\) với \(|a_i| \leq 1000\).

• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo một trong ba định dạng sau:

• 2 u v \((1 \leq u \leq v \leq N)\).

• 1 u v x \((1 \leq u \leq v \leq N, -1000 \leq x \leq 1000)\).
• 0 u v x \((1 \leq u \leq v \leq N, -1000 \leq x \leq 1000)\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng các bình phương phần tử trong đoạn \([u, v]\) tại thời điểm đó.

Example

5 5
2 3 1 5 4
2 3 5
1 1 5 -2
2 1 4
0 2 4 3
2 1 5

42
11
31

Scoring

• Subtask \(1\) (25% số điểm) : \(N, Q \leq 1000\).
• Subtask \(2\) (25% số điểm) : Không có thao tác loại \(1\).
• Subtask \(3\) (25% số điểm) : Không có thao tác loại \(0\).
• Subtask \(4\) (25% số điểm) : Không có ràng buộc gì thêm.

Trong một ngôi làng nhỏ, có một truyền thuyết về hai con số kỳ diệu \(a\) và \(b\), được gọi là cặp số LTN. Theo truyền thuyết, cặp số này thỏa mãn điều kiện:

với \(X\) là một số nguyên dương được các trưởng làng lựa chọn cẩn thận.

Một ngày nọ, Eldric - cậu bé thông minh nhất làng - được giao nhiệm vụ giải mã bài toán LTN. Eldric cần phải tìm ra tất cả các cặp số \(a, b\) là cặp số LTN thỏa mãn điều kiện trên. Tuy nhiên, với số \(X\) lớn, nhiệm vụ này không hề dễ dàng.

\textbf Yêu cầu: Hãy giúp Eldric xác định có bao nhiêu cặp số \((a, b)\) thỏa mãn điều kiện của một cặp số LTN.

Input

• Dòng đầu tiên chứa một số nguyên \(T\) \((1 \leq T \leq 10^5)\), là số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(X\) \((1 \leq X \leq 10^6)\).

Output

• \(30\%\) số điểm ứng với \(1 \leq T \leq 10^3\), \(1 \leq X \leq 100\).
• \(30\%\) số điểm ứng với \(1 \leq T \leq 10^3\), \(1 \leq X \leq 10^6\).
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Example

1
2

6