Bài tập

Xét \(x = (x_{1}, x_{2}, . . . , x_{m})\) là một dãy số. Phép dịch trái là chuyển phần tử đầu của dãy xuống cuối dãy. Dãy \(x\) sau khi thực hiện dịch trái \(k\) lần là \((x_{k+1}, x_{k+2}, . . . , x_{m}, x_{1}, x_{2}, . . . , x_{k})\). Dãy \(x\) được gọi là shlgood nếu \(m\) chẵn và có thể dịch trái một số lần (có thể là \(0\) lần) sao cho \(\frac{m}{2}\) phần tử đầu của dãy lớn hơn hẳn \(\frac{m}{2}\) phần tử cuối của dãy, tính từ trái sang phải. Cụ thể, dãy \(x\) là shlgood nếu tồn tại số nguyên không âm \(k\) sao cho sau khi dãy \(x\) dịch trái \(k\) lần, ta thu được dãy \(y\) thoả mãn \(y_{i} > y_{j}\) \(∀1 ≤ i ≤ \frac{m}{2} < j ≤ m\).

Cho dãy số nguyên \(a = (a_{1}, a_{2}, . . . , a_{n})\), hãy đếm số dãy con liên tiếp của a là dãy shlgood.

Input

• Dòng đầu tiên chứa số nguyên dương: \(n\);

• Dòng tiếp theo chứa \(n\) số nguyên: \(a_{1}, a_{2}, . . . , a_{n}\)

Output

Ghi một số nguyên duy nhất là số dãy con liên tiếp là dãy shlgood của \(a\).

Example

6
1 3 2 6 4 5

7

Scoring

• Trong tất cả các test: \(1 ≤ n ≤ 5 × 10^5, −10^9 ≤ a_{i} ≤ 10^9\).

• Có \(12\%\) số test với \(n ≤ 500\);

• Có \(24\%\) số test với \(n ≤ 5000\);

• Có \(20\%\) số test với \(a_{i}\) đôi một phân biệt;

• Có \(44\%\) số test với ràng buộc gốc.

Alice sở hữu một khu vườn táo thần kỳ hình chữ nhật kích thước \(N \times M\). Khu vườn được chia thành lưới ô vuông, các hàng được đánh số từ \(1\) đến \(N\), các cột được đánh số từ \(1\) đến \(M\). Tại ô đất ở hàng \(i\), cột \(j\), có một cây táo đang trĩu quả với số lượng là \(a_{i,j}\).

Để thu hoạch táo, Alice sử dụng một loại robot thông minh. Nếu robot được đặt tại vị trí \((u, v)\), nó có khả năng vươn tay hái toàn bộ số táo ở các ô \((x, y)\) thỏa mãn khoảng cách Manhattan đến vị trí đứng không vượt quá \(k\). Tức là:

Tuy nhiên, khu vườn này có phép thuật. Tại một số thời điểm bất kỳ, số lượng táo trên một cây tại vị trí \((x, y)\) có thể thay đổi đột ngột (do táo chín thêm hoặc bị rụng bớt).

Alice cần thực hiện một chuỗi các công việc gồm hai loại:

• Loại 1 (Thu hoạch): Đặt robot tại vị trí \((x, y)\) với tầm với \(k\), hãy tính tổng số táo mà robot có thể thu hoạch được.
• Loại 2 (Cập nhật): Số lượng táo tại ô \((x, y)\) thay đổi thành giá trị mới là \(val\).

Hãy giúp Alice quản lý khu vườn và tính toán sản lượng thu hoạch.

Input

Dữ liệu vào từ tệp văn bản APPLE.INP:

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) (\(N, M \le 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên dương. Số thứ \(j\) trên dòng thứ \(i\) là \(a_{i,j}\) (\(a_{i,j} \le 1000\)).
• Dòng tiếp theo chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^4\)) là số lượng truy vấn.

• \(Q\) dòng tiếp theo mô tả các truy vấn theo định dạng:

• 1 x y k: Truy vấn thu hoạch tại \((x, y)\) với tầm xa \(k\) (\(0 \le k \le 1000\)).

• 2 x y val: Cập nhật số táo tại \((x, y)\) thành \(val\) (\(1 \le val \le 10^5\)).

• Dữ liệu đảm bảo toạ độ \((x, y)\) luôn hợp lệ (\(1 \le x \le N, 1 \le y \le M\)).

Output

Ghi ra tệp văn bản APPLE.OUT:

• Với mỗi truy vấn loại 1, in ra một dòng chứa tổng số táo thu hoạch được.

Example

3 3
1 1 1
1 10 1
1 1 1
3
1 2 2 1
2 2 2 5
1 2 2 1

14
9

Scoring

• Subtask 1 (\(25\%\) số điểm): \(N, M \le 100\).
• Subtask 2 (\(25\%\) số điểm): \(k \le 20\).
• Subtask 3 (\(25\%\) số điểm): Không có truy vấn loại 2 (Cập nhật).
• Subtask 4 (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Đất nước \(X\) có \(n\) bưu cục, các bưu cục lần lượt được đánh số từ \(1\) tới \(n\) và lần lượt nằm trên các điểm \(1\), \(2\), \(3\), ..., \(n\) trên trục số.

Bưu cục \(i\) có thể gửi thư tới bưu cục \(j\) nếu khoảng cách giữa chúng không vượt quá \(p_{i}\). Bưu cục \(i\) có thể nhận thư từ bưu cục \(j\) nếu khoảng cách giữa chúng không vượt quá \(p_{i}\). Vì công nghệ hiện tại quá tối tân, dù khoảng cách có xa cỡ nào thì việc gửi thư và nhận thư chỉ cần thực hiện trong \(1\) giây.

Có một lá thư đang nằm ở bưu cục \(a\) và cần chuyển đến bưu cục \(b\), hỏi thời gian ngắn nhất để bưu cục \(b\) nhận được thư là bao lâu ?

Input

Dòng đầu tiên gồm \(3\) số nguyên dương \(n, a, b\). \((a, b <= n\), \(n <= 2.10^5)\)

Dòng tiếp theo gồm \(n\) số nguyên dương \(p_{1}, p_{2}, ..., p_{n}\).

Output

Kết quả bài toán.

Example

10 2 9
4 1 1 1 5 1 1 1 1 5

4

Scoring

\(40\%\) số test có \(n <= 1000\).

\(60\%\) số test có \(n <= 200000\).

Cho dãy số nguyên \(a\) gồm \(n\) số nguyên. Số nghịch thế của \(a\) là số cặp \(i, j\) sao cho \(1 ≤ i < j ≤ n\) và \(a_{i} > a_{j}\) . Ta thực hiện \(Q\) biến đổi trên \(a\), mỗi biến đổi có dạng:

Tăng \(a_{i}\) lên một lượng bằng x.

Yêu cầu in ra sau số nghịch thế của \(a\) sau mỗi truy vấn

Input

• Dòng đầu chứa \(n, Q\)

• Dòng tiếp theo chứa \(n\) số tự nhiên: \(a_{1}, a_{2}, . . . , a_{n}\)

• \(Q\) dòng tiếp theo mỗi dòng chứa \(i, s\). Công thức tính \(x\) là: \(x = |s + sum|\%(2 × 10^9 + 1) − 10^9\). Ở đây sum là tổng các kết quả của các truy vấn trước truy vấn này

Output

Gồm \(Q\) dòng ghi kết quả tương ứng

Example

4
1 2 3 4
2
3 999999998
3 1000000003

1
1

Scoring

\(1 ≤ n, Q ≤ 10^5, 0 ≤ s ≤ 2 × 10^9\), \(−10^9 ≤ a_{i} ≤ 10^9\) trong mọi thời điểm

• \(30\%\) test: \(n, Q ≤ 10^4\)