Nghịch thế chữ cái

Cho một xâu \(s\) độ dài \(n\) chỉ gồm các ký tự Latin in thường (từ a đến z). Có \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(l\) và \(r\), hãy đếm có bao nhiêu cặp nghịch thế trong xâu con liên tiếp từ \(l\) đến \(r\).

Số cặp nghịch thế là số cặp \(i\), \(j\) sao cho \(i < j\) và ký tự ở vị trí \(i\) nằm sau ký tự ở vị trí \(j\) trong thứ tự từ điển. Ví dụ, xâu beac có \(3\) cặp nghịch thế, đó là \((1, 3)\), \((2, 3)\) và \((2, 4)\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \times 10^5)\) là độ dài của xâu.

• Dòng tiếp theo chứa xâu \(s\) có độ dài \(n\) chỉ gồm các ký tự Latin in thường.

• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 5 \times 10^5)\) là số truy vấn.

• Trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq n)\) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, mỗi dòng là số cặp nghịch thế của truy vấn tương ứng.

Example

7
adbcedc
4
1 4
3 5
4 7
2 4

2
0
3
2

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^2\).

• Subtask \(2\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^3\).

• Subtask \(3\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^4\).

• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.