TDZ quyết định đi mua đồ chơi mới sau khi đã chán đồ chơi cũ. Cửa hàng đồ chơi hiện đang bán ~N~ mặt hàng đồ chơi, mặt hàng thứ ~i~ có giá tiền ~A_i~. Tuy nhiên, cửa hàng đang bán rất chạy nên chỉ cho phép mỗi khách mua chính xác ~2~ bộ khác nhau (có thể mua một mặt hàng ~2~ lần).

Bạn cần trả lời ~Q~ truy vấn khác nhau: Giả sử TDZ đang có số tiền là ~X~ trong tay, có bao nhiêu cách mà TDZ mua được ~2~ bộ đồ chơi?

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 2 \times 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ - giá tiền các mặt hàng (~A_i \leq 10^6~).
• Dòng thứ ba chứa số nguyên dương ~Q~ - số lượng truy vấn (~Q \leq 1000~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~X~ (~X \leq 2 \times 10^6~).

Output

• Với mỗi truy vấn, in ra số cách để TDZ mua 2 đồ chơi trên từng dòng khác nhau.

Sample Test

Input:

5
1 2 4 3 5
3
4
6
8

Output:

4
9
13

Note:

• Ở truy vấn thứ nhất, TDZ có 4 cách mua:
  • Mua ~2~ bộ mặt hàng ~1~;
  • Mua ~2~ bộ mặt hàng ~2~;
  • Mua ~1~ bộ mặt hàng ~1~ và ~1~ bộ mặt hàng ~2~;
  • Mua ~1~ bộ mặt hàng ~1~ và ~1~ bộ mặt hàng ~4~.

Cho dãy ~A~ gồm ~n~ phần tử, phần tử thứ ~i \ (1 \le i \le n)~ có giá trị ~a_i~.

Bạn có thể biến đổi dãy ~A~ bằng thao tác sau: Chọn hai phần tử liên tiếp trong dãy và thay thế hai phần tử này bằng tổng của chúng.

Hãy đếm số lượng thao tác tối thiểu để dãy ~A~ là dãy đối xứng. Dãy ~A~ được coi là dãy đối xứng nếu đọc từ phải sang trái vẫn thu được dãy ~A~ ban đầu.

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 dương ~a_i \ (1 \le a_i \le 10^9)~.

Output

In ra kết quả là số thao tác tối thiểu để dãy ~A~ là dãy đối xứng.

Scoring

• Subtask 1 [30%]: ~n \le 10;~
• Subtask 2 [30%]: ~n \le 1000;~
• Subtask 3 [40%]: ~n \le 10^6.~

Examples

Input

3
1 2 3

Output

1

Giải thích: ~\textbf{1 2} \ 3 \rightarrow 3 \ 3.~

Input

5
1 2 4 6 1

Output

1

Giải thích: ~1 \ {\textbf{2 4}} \ 6 \ 1 \rightarrow 1 \ 6 \ 6 \ 1~.

Input

4
1 4 3 2

Output

2

Giải thích: ~\textbf{1 4} \ 3 \ 2 \rightarrow 5 \ \textbf{3 2} \ \rightarrow 5 \ 5~.

Cho một dãy số ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. Một dãy con liên tiếp từ ~L~ đến ~R~ của dãy số ~A~ là các phần tử ~A_L,A_{L+1},…,A_{R-1},A_R~ ~(1≤L≤R≤N)~. Cho một số nguyên dương ~T~, hãy đếm xem có bao dãy con của ~A~ có tổng các phần tử không quá ~T~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~T~ là số lượng phần tử của dãy số ~A~ và số ~T~ cho trước ~(N≤10^6; T≤10^9)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_i~ mô tả các phần tử của dãy số ~A~ ~(1≤i≤N; A_i≤10^9)~.

Output:

Một số nguyên duy nhất là số lượng dãy con thoả mãn yêu cầu đề bài.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm có ~N≤100~;
• Có 30% số test khác tương ứng với 30% số điểm có ~N≤5000~;
• 20% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

6 8
8 3 2 1 6 9

Output

9

Giải thích

Các dãy con thoả mãn: ~\{8\},\{3\},\{2\},\{1\},\{6\},\{3,2\},\{2,1\},\{1,6\},\{3,2,1\}~

Công ty đồ chơi X nhập khẩu ~n~ con búp bê gỗ. Các con búp bê được đánh số từ ~1~ tới ~n~ trong đó con búp bê thứ ~i~ là một hộp rỗng có kích thước là một số nguyên ~a_i~. Người ta có thể lồng con búp bê thứ ~i~ vào trong con búp bê thứ ~j~ nếu con búp bê thứ ~j~ đang rỗng và ~a_i + k ≤ a_j~, với ~k~ là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty X chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.

Yêu cầu: Hãy giúp công ty X lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.

Input

Gồm 2 dòng

• Dòng 1 chứa hai số nguyên dương ~n ≤ 10^5~; ~k ≤ 10^9~ cách nhau một khoảng trắng.

• Dòng 2 chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ( ~a_i ≤ 10^9~), mỗi số cách nhau một khoảng trắng.

Output

• Là một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.

Sample Test

Input

8 2
8 4 2 1 1 3 5 9

Output

18

Một dãy số được gọi là ~''~đẹp~''~ nếu mỗi phần tử trong dãy đó đều có số lần xuất hiện không vượt quá ~2~. Ví dụ:

• ~[1, 5, 2, 4, 3], [6, 9, 9, 6], [100]~ là các dãy đẹp.
• ~[3, 3, 3, 4, 4], [7, 7, 8, 7]~ và ~[100, 100, 100]~ không phải là các dãy đẹp.

Cho dãy ~a~ có ~n~ phần tử, hãy đếm số cặp chỉ số ~(l, r)~ sao cho ~a_l, a_{l+1}, ..., a_r~ là dãy đẹp.

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 dương ~a_1, a_2, ..., a_n.~

Output

In ra kết quả là số cặp chỉ số ~(l, r)~ thoả mãn đề bài.

Scoring

• Subtask 1 [20%]: ~n \le 50; \ a_i \le 50;~
• Subtask 2 [15%]: ~n \le 500; \ a_i \le 500;~
• Subtask 3 [15%]: ~n \le 5000; \ a_i \le 5000;~
• Subtask 4 [50%]: ~n \le 5 \times 10^5; \ a_i \le 5 \times 10^5.~

Examples

Input

4
1 2 1 1

Output

9

Giải thích: Các cặp chỉ số ~(l, r)~ thoả mãn đề bài là: ~(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).~

Input

6
4 5 4 5 4 5

Output

18

Bạn được cho một mảng gồm ~n~ số nguyên và nhiệm vụ của bạn là tìm ba giá trị (tại các vị trí phân biệt) có tổng là ~x~.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~x~: kích thước mảng và tổng mong muốn.
• Dòng thứ hai có ~n~ số nguyên ~a_1,a_2,\ldots,a_n~: các giá trị của mảng.

Output

• In ba số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

• ~1 \leq n \leq 5000~
• ~1 \leq x, a_i \leq 10 ^ 9~

Example

Sample input

4 8
2 7 5 1

Sample output

1 3 4

Cho dãy số nguyên ~A~ gồm ~N~ phần tử ~A_{1}, A_{2}, \ldots, A_{N}~ và một số nguyên ~K~.

Yêu cầu: Đếm số cặp số ~L, R~ ~(1 \leq L \leq R \leq N)~ sao cho dãy con liên tiếp ~A_{L}, A_{L + 1}, \ldots, A_{R}~ có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá ~K~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(N \leq 10^{5}, K \leq 10^{18})~
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_{1}, A_{2}, \ldots, A_{N}~ ~(|A_{i}| \leq 10^{9})~.

Outputs

• In ra một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~N \leq 100~.
• Subtask ~2~ (~20\%~ số điểm): ~N \leq 5000~.
• Subtask ~3~ (~30\%~ số điểm): không có ràng buộc gì thêm.

Sample Test

Input

5 2
2 -1 3 1 3

Output

8