Beautiful Sequence

Alexander là 1 người rất thích cái đẹp. Vẻ đẹp từ những loài hoa, những vì sao, những con số đều làm Alexander mê mẩn. Sau nhiều năm nghiên cứu về vẻ đẹp, Alexander phát hiện ra những con số đều mang 1 ý nghĩa nào đó của vũ trụ, như số cánh hoa, số vòng xoáy trên mỗi thiên hà quan sát được từ vũ trụ, chúng đều là số Fibonacci. Hiểu được tâm lý của Alexander, thầy X (thành viên của tổ chức trí tuệ Mensa) đã đố anh 1 bài toán. Bài toán như sau:

Cho 1 dãy N loài hoa từ 1 tới N được sắp xếp từ trái sang phải. Flower = (1, 2, ..., N). Thầy X chọn 2 loài hoa trong N loài hoa trên và đổi chỗ chúng. Một phép đổi chỗ gọi là “Beautiful” nếu tồn tại 1 số tự nhiên M (1 ≤ M < N) sao cho tổng M loài hoa đầu tiên bằng tổng N – M loài hoa cuối cùng. Nhiệm vụ của bạn là hãy tính số phép đổi chỗ “Beautiful”.

Ví dụ: 

• Xét N = 3. Lúc này ta có Flower = (1,2,3). Ta có 2 phép đổi chỗ “Beautiful”):
  • Phép 1: Phép đổi chỗ loài hoa 1 và loài hoa 3. Lúc này ta có Flower = (3, 1, 2). Phép này “Beautiful” vì tồn tại M = 1 thỏa mãn tính chất của phép đổi “Beautiful”.
  • Phép 2: Phép đổi chỗ loài hoa 1 và loài hoa 2. Lúc này ta có Flower = (2, 1, 3). Phép này “Beautiful” vì tồn tại M = 2 thỏa mãn tính chất của phép đổi “Beautiful”.
  • Lúc này với N = 3, ta có đáp án là 2 phép biến đổi “Beautiful”.

[Đầu vào/Đầu ra]:

• [Giới hạn thời gian]: 1s với C++, 6s với Java & C#, 8s với Python,Go,Js.
• [Đầu vào]: 
  • Số tự nhiên T (1 ≤ T ≤ 106) biểu thị số truy vấn.
  • Array of Integer a, bao gồm T số, mỗi số biểu thị 1 số tự nhiên ai  , (1 ≤ ai ≤ 109) là số loài hoa được đưa ra. Nhiệm vụ của bạn là trả lời với mỗi truy vấn.
• [Đầu ra]:
  • 1 vector gồm T số tương ứng với số T truy vấn.