FullHouse Dev và Mảng con

Bối cảnh

FullHouse Dev đang nghiên cứu về các mảng con trong một dãy số. Họ có một mảng A gồm N số nguyên và Q truy vấn. Mỗi truy vấn chứa một số nguyên K, và nhiệm vụ là đếm số lượng mảng con thỏa mãn điều kiện: hàm foo trả về K khi áp dụng cho mảng con đó.

Yêu cầu

Trong bài toán này, mảng con được định nghĩa là một dãy các phần tử liên tiếp Ai, Ai+1, ..., Aj trong đó 0 ≤ i ≤ j ≤ N-1. Hàm foo, khi áp dụng cho một mảng, sẽ trả về giá trị nhỏ nhất trong tất cả các phần tử của mảng đó.

Hãy giúp FullHouse Dev giải quyết bài toán này!

Input

• Dòng đầu tiên chứa số nguyên N - kích thước của mảng.
• Dòng thứ hai chứa N số nguyên A0, A1, ..., AN-1 cách nhau bởi dấu cách, biểu thị các phần tử của mảng.
• Dòng thứ ba chứa số nguyên Q - số lượng truy vấn.
• Q dòng tiếp theo, mỗi dòng chứa một số nguyên K biểu thị một truy vấn.

Output

• Với mỗi truy vấn, in ra số lượng mảng con thỏa mãn điều kiện.

Ràng buộc

• \(1 ≤ N ≤ 50\)
• \(1 ≤ Ai ≤ 1000000 (10^6)\)
• \(1 ≤ Q ≤ 10\)
• \(1 ≤ K ≤ 1000000 (10^6)\)

Ví dụ 1

Input

5
4 1 2 3 4
4
3
4
6
1

Output

2
2
0
8

Giải thích ví dụ

• Truy vấn 1: Chỉ có hai mảng con [3, 4] và [3] thỏa mãn.
• Truy vấn 2: Chỉ có hai mảng con [4] và [4] thỏa mãn. Lưu ý rằng các mảng con này (A0 và A4) được coi là khác nhau.
• Truy vấn 3: Không có mảng con nào thỏa mãn.
• Truy vấn 4: Có tám mảng con thỏa mãn: [4, 1], [4, 1, 2], [4, 1, 2, 3], [4, 1, 2, 3, 4], [1], [1, 2], [1, 2, 3] và [1, 2, 3, 4].

Thông tin học tập

• Buổi: B10
• Concepts: 1D arrays, subarray traversal, small queries
• Giới hạn kiến thức: B01-B10
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 25