Alice tạo dãy số nguyên ~a_1, a_2, \dots, a_N~, cô cần thống kê số bộ ba chỉ số ~(i, j, k)~ thỏa mãn hai điều kiện sau:

• ~1 \le i < j < k \le N~;
• ~a_i \le a_j \ge a_k~ hoặc ~a_i \ge a_j \le a_k~.

Yêu cầu

Cho dãy gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~, hãy đếm số lượng bộ ba thỏa mãn.

Input

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

Output

Một số nguyên là số lượng bộ ba thỏa mãn.

Scoring

• Subtask 1 (10% số điểm): ~N = 3~
• Subtask 2 (30% số điểm): ~N \le 300~
• Subtask 3 (30% số điểm): ~N \le 3000~
• Subtask 4 (30% số điểm): Không có ràng buộc nào thêm

Ví dụ

Input 1

3
1 2 3

Output 1

0

Input 2

4
1 3 2 4

Output 2

2

Input 3

4
1 1 1 1

Output 3

4

Cho Alice mới tạo ra một trò chơi tìm đường đi trên mặt phẳng tọa độ. Cụ thể, một nhân vật xuất phát tại vị trí ~(x_s, y_s)~ cần di chuyển tới vị trí ~(x_t, y_t)~ trong thời gian ngắn nhất. Tại mỗi đơn vị thời gian, giả sử nhân vật đang ở vị trí ~(x_1, y_1)~ thì có thể di chuyển tới vị trí ~(x_2, y_2)~ nếu ~\max(|x_1 - x_2|, |y_1 - y_2|) = 1~. Để trò chơi thêm thú vị, Alice đặt ~K~ vật phẩm ở ~K~ vị trí ~(u_1, v_1), (u_2, v_2), \dots, (u_K, v_K)~, ngoài việc di chuyển với thời gian ngắn nhất, người chơi cần chọn đường đi để thu thập được nhiều vật phẩm nhất. Nhân vật di chuyển tới vị trí có vật phẩm sẽ thu thập được vật phẩm ở vị trí đó và thời gian thu thập là không đáng kể.

Yêu cầu: Cho các thông tin ~(x_s, y_s), (x_t, y_t)~ và ~(u_1, v_1), (u_2, v_2), \dots, (u_K, v_K)~, hãy tìm đường đi từ vị trí ~(x_s, y_s)~ đến ~(x_t, y_t)~ với thời gian ngắn nhất, trong số các đường đi ngắn nhất đó, chọn con đường đi qua nhiều vị trí chứa vật phẩm nhất.

Input

Dữ liệu vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• Dòng đầu chứa năm số nguyên ~x_s, y_s, x_t, y_t, K~ (~|x_s|, |y_s|, |x_t|, |y_t| \le 10^9~; ~K \le 10^5~);
• Dòng thứ ~i~ trong ~K~ dòng sau chứa hai số nguyên ~u_i, v_i~ (~|u_i|, |v_i| \le 10^9~). Vị trí các vật phẩm là phân biệt và khác với vị trí xuất phát cũng như vị trí đích.

Output

Kết quả ghi ra thiết bị ra chuẩn (màn hình) gồm một số nguyên không âm là số vật phẩm nhiều nhất có thể thu thập được.

Giới hạn

• Subtask 1 (25%): ~K \le 10~
• Subtask 2 (25%): ~K \le 20~
• Subtask 3 (25%): ~K \le 3000~
• Subtask 4 (25%): Không có ràng buộc nào thêm.

Ví dụ

Input 1

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

Output 1

3

Giải thích 1: ~(0, 0) \to (1, 1) \to (2, 0) \to (3, -1) \to (4, 0)~

Input 2

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

Output 2

3

Giải thích 2: ~(0, 0) \to (1, 1) \to (2, 0) \to (3, -1) \to (4, 0)~

Input 3

0 0 2 2 1
0 1

Output 3

0

Giải thích 3: ~(0, 0) \to (1, 1) \to (2, 2)~ ```

Alice có ~N~ bình nước giống nhau, mỗi bình có thể chứa được ~V~ lít nước. Hiện tại, bình thứ ~i~ (~1 \le i \le N~) chứa ~v_i~ lít nước (~v_1 + v_2 + \dots + v_N = V~). Alice muốn thực hiện một dãy các lần đổ nước giữa các bình để số lượng bình rỗng là nhiều nhất. Mỗi lần cô có thể đổ nước từ bình ~i~ sang bình ~j~ nếu ~v_i \ge v_j~ một lượng nước bằng ~v_j~ lít, sau khi đổ bình ~i~ còn ~v_i - v_j~ lít, bình ~j~ có ~2v_j~ lít.

Yêu cầu: Hãy tìm một dãy các lần đổ nước để số lượng bình rỗng là nhiều nhất.

Input

Dữ liệu vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• Dòng đầu chứa số nguyên ~T~ (~T \le 10~) là số bộ dữ liệu, tiếp theo là các nhóm dòng, mỗi nhóm có khuôn dạng:
  • Dòng đầu chứa số nguyên dương ~N~ (~2 \le N \le 10~).
  • Dòng thứ hai chứa ~N~ số nguyên dương ~v_1, v_2, \dots, v_N~ (~v_1 + v_2 + \dots + v_N = V \le 10^{12}~).

Output

Kết quả ghi ra thiết bị ra chuẩn (màn hình) gồm ~T~ nhóm dòng, mỗi nhóm mô tả lời giải tương ứng một bộ dữ liệu theo khuôn dạng:

• Dòng đầu ghi số nguyên ~S~ là số lần đổ nước;
• Dòng thứ ~t~ (~1 \le t \le S~) trong ~S~ dòng sau, mỗi dòng ghi hai số ~i, j~ cho biết lần đổ thứ ~t~ đổ nước từ bình ~i~ sang bình ~j~.

Ràng buộc

• Subtask 1 (20%): ~N = 3~ và ~V \le 300~.
• Subtask 2 (20%): ~N = 3~ và ~V \le 3000~.
• Subtask 3 (20%): ~V \le 3000~.
• Subtask 4 (20%): ~N = 3~.
• Subtask 5 (20%): Không có ràng buộc nào thêm.

Ví dụ

Input

2
3
1 2 3
4
1 1 1 1

Output

2
3 1
2 3
3
4 3
2 1
3 1

Giải thích:

• Với bộ dữ liệu thứ nhất có thể nhận được 1 bình rỗng: ~(1, 2, 3) \to (2, 2, 2) \to (2, 0, 4)~.
• Với bộ dữ liệu thứ hai có thể nhận được 3 bình rỗng: ~(1, 1, 1, 1) \to (2, 0, 2, 0) \to (4, 0, 0, 0)~. ```

Lưu ý: testcase bài này vẫn còn khá yếu.

Một cây táo được biểu diễn bằng một đồ thị dạng cây. Đồ thị liên thông có ~N~ đỉnh và ~N - 1~ cạnh, trong đó đỉnh thứ ~i~ (~1 \le i \le N~) có trọng số là số nguyên dương ~w_i~ biểu diễn có một quả táo ở vị trí đó với khối lượng là ~w_i~ (gram). Alice chỉ có thể mang được không quá ~S~ gram nên cô muốn chọn hái một số quả táo thỏa mãn:

1) Tổng khối lượng các quả chọn hái là không quá ~S~.

2) Hai quả được chọn hái không kề nhau.

Yêu cầu: Hãy chọn hái các quả để tổng khối lượng các quả càng lớn càng tốt.

Dữ liệu: Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương ~N, S~ (~N \le 1000; S \le 10^9~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~w_1, w_2, \dots, w_N~ (~w_i \le 10^9~).
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le N~) mô tả các cạnh của cây. Dữ liệu đảm bảo luôn tồn tại cách chọn để đạt được tổng bằng ~S~.

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) theo khuôn dạng:

• Dòng đầu ghi số nguyên ~K~ là số quả chọn hái.
• Dòng thứ hai chứa ~K~ số chỉ số các quả chọn hái.

Giới hạn

• Subtask 1 (20%): ~N \le 40~; ~S \le 10^4~ và cây có dạng đường thẳng.
• Subtask 2 (20%): ~N \le 40~; ~S \le 10^4~.
• Subtask 3 (20%): ~S \le 10^6~ và cây có dạng đường thẳng.
• Subtask 4 (30%): ~S \le 10^6~.
• Subtask 5 (10%): Không có ràng buộc nào thêm.

Cách chấm điểm

Đây là bài toán chấm điểm theo tỉ lệ tối ưu. Gọi tổng khối lượng các quả táo chọn hái do thí sinh tìm được là ~P~, khi đó phần trăm số điểm đạt được cho mỗi test là ~\frac{P}{S} \times 100\%~.

Ví dụ

Input

5 10
3 7 2 8 5
1 2
2 3
3 4
4 5

Output

3
1 3 5

Giải thích: Chọn hái quả 1, 3 và quả 5, tổng khối lượng là ~3 + 2 + 5 = 10~. ```