Yakumo Ran rất thích làm toán, hôm nay cô nghiên cứu bài toán sau:

Cho một mảng ~a~ có ~n~ phần tử, cho ~q~ truy vấn dạng l r x, hãy đếm số lượng số có giá trị ~x~ trong đoạn ~a[l...r]~.

Hiện tại cô chưa có lời giải cho bài toán này nên nhờ các bạn giúp!

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n, q \le 10^5~.
• Dòng tiếp theo là mảng ~a~ nguyên với ~1 \le a_i \le 10^9~.
• ~q~ dòng tiếp theo mỗi dòng gồm 3 số ~l_i, r_i, x_i~ là truy vấn thứ ~i~.

Output

• Với mỗi truy vấn in ra kết quả.

Sample Test

Input:

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

Output:

2
1

Trò chơi Bắc Nam không phải là trò chơi của miền Bắc và miền Nam mà là trò chơi giữa hai bạn Bắc và Nam. Hai bạn Bắc và Nam quen nhau trong một cuộc thi lập trình danh giá. Hai bạn đều được giải cao. Điều thú vị là Bắc quê ở miền Nam còn Nam quê ở miền Bắc. Trong buổi lễ trao phần thưởng, Ban tổ chức cuộc thi có tổ chức một trò chơi trí tuệ dành cho những bạn đạt giải. Mỗi lượt chơi gồm ~2~ bạn chơi. Bắc và Nam cùng chơi một lượt. Nội dung trò chơi được phát biểu:

Cho một vòng tròn được chia thành ~n~ vạch cách đều (~n~ là một số chẵn). Các vạch được đánh chỉ số từ ~1~ đến ~n~ theo chiều kim đồng hồ. Tại vạch ~i~ có ghi một số nguyên dương ~a_i (1 \le a_i \le n)~. Dãy gồm ~n~ số ~a_1,a_2,…,a_n~ tạo thành một hoán vị của ~n~ số nguyên ~1,2,3,…,n~. Hai bạn Bắc và Nam đều phải lập trình điều khiển robot di chuyển quanh vòng tròn để xóa số.

Robot của Bắc xuất phát từ vạch ~1~, di chuyển theo chiều kim đồng hồ. Khi robot đến vạch nào thì có thể xóa số ở vạch đó, tuy nhiên các số mà robot của bạn Bắc cần xóa lần lượt là ~1,3,5,...,n – 1~. Tức là số ~1~ sẽ được xóa đầu tiên, rồi đến số ~3,...,~ số ~n – 1~ sẽ được xóa cuối cùng. Khi xóa xong, robot sẽ di chuyển đến vạch ~1~ và dừng lại. Robot của Bắc chỉ được xóa các số lẻ.

Robot của Nam cũng xuất phát từ vạch ~1~, di chuyển theo chiều kim đồng hồ. Khi robot đến vạch nào thì có thể xóa số ở vạch đó, tuy nhiên các số mà robot của bạn Nam cần xóa lần lượt là ~2,4,6,...,n~. Tức là số ~2~ sẽ được xóa đầu tiên, rồi đến số ~4,...,~ số ~n~ sẽ được xóa cuối cùng. Khi xóa xong, robot sẽ di chuyển đến vạch ~1~ và dừng lại. Robot của Nam chỉ được xóa các số chẵn.

Bạn Bắc và Nam cần đưa ra số vòng mà robot của mình cần di chuyển quanh vòng tròn để xóa hết tất cả các số cần xóa. Bạn nào đưa ra kết quả đúng và nhanh sẽ được điểm cao và được nhận được nhiều phần quà có giá trị của Ban tổ chức.

Input

• Dòng ~1~ ghi số nguyên dương chẵn ~n~ ~(2 ≤n≤200000)~.
• Dòng ~2~ ghi ~n~ số nguyên dương ~a_1,a_2,…,a_n~ là một hoán vị của ~n~ số ~1,2,3,…,n~. Các số được ghi cách nhau bởi dấu cách.

Output

• Dòng ~1~ ghi số vòng mà robot của bạn Bắc cần di chuyển quanh vòng tròn để lần lượt xóa hết tất cả các số ~1,3,5,...,n – 1~.
• Dòng ~2~ ghi số vòng mà robot của bạn Nam cần di chuyển quanh vòng tròn để lần lượt xóa hết tất cả các số ~2,4,6,...,n~.

Subtask

• Có ~25\%~ số test ứng với ~n = 8~.
• Có ~25\%~ số test ứng với ~n \le 1000~.
• ~50~ số test còn lại không giới hạn gì thêm.

  Sample Input 1

8
1 7 3 2 4 6 5 8

Sample Output 1

2
1

Explanation 1

• Robot của Bắc:
  • Vòng ~1~: Xóa các số: ~1, 3, 5~.
  • Vòng ~2~: Xóa số ~7~.
• Robot của Nam:
  • Vòng ~1~: Xóa các số: ~2, 4, 6, 8~.

Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài ~n~ gồm cách kí tự ~a, b, c~ (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.

Cô đang nghi ngờ ~q~ đoạn con ~[l_i, r_i]~ có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ ~aab~ là không thỏa mãn vì có ~aa~ là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!

Input:

• Dòng đầu tiên gồm 2 số ~n, q~.
• Dòng tiếp theo là một xâu gồm ~n~ kí tự chỉ gồm ~a, b, c~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~l_i, r_i~.

Output:

• ~q~ dòng là chi phí chữa bệnh.

Sample Test

Input:

5 4
baacb
1 3
1 5
4 5
2 3

Output:

1
2
0
1

Giới hạn:

• Trong mọi test ~n, q \le 10^5~
• 10% số điểm: ~n, q \le 5~.
• 30% số điểm: ~n, q \le 2000~.
• 30% số điểm: ADN chỉ gồm 2 kí tự ~a, b~.
• 30% số điểm: Không có giới hạn gì thêm.

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tìm cách chia dãy ~a~ ra thành ít dãy con (không nhất thiết liên tiếp) nhất, sao cho các dãy con đều là dãy không giảm và mỗi phần tử của ~a~ thuộc đúng một dãy con.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 10^5)~

• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~. (~a_i \le 10^9~)

  Output

• In ra số lượng dãy con ít nhất thỏa mãn.

Sample Test

Input:

4
1 5 4 6

Output:

2

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12

Cho số nguyên dương ~N~. Đếm xem có bao nhiêu cặp số nguyên ~[a,b]~ ~(0 < a \le b)~ để tổng các số nguyên trong đoạn ~[a,b]~ bằng ~N~. Hai đoạn khác nhau là hai đoạn có ít nhất một phần tử khác nhau.

Input

• Gồm một dòng duy nhất chứa số nguyên dương ~N~.

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Subtask

• Subtask ~1~ (~40\%~ số điểm): ~n \le 10^4~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 10^8~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^{15}~

Sample Input 1

9

Sample Output 1

3

Explanation 1

~3~ đoạn thỏa mãn là : ~[2,4]~, ~[4,5]~, ~[9,9]~.

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Người thầy quốc dân Gojo Satoru giờ đang có một niềm đam mê với tin học. Để lan tỏa điều này, anh muốn đố các học sinh của mình một bài toán như sau: Cho một dãy số nguyên ~a~ gồm ~n~ phần tử, định nghĩa ~f(l,r)~ là ~max(a_i) - min(a_i) \forall (l \le i \le r)~.

Hãy tính tổng của ~f(l,r) \forall (1 \le l \le r \le n)~.

Tất nhiên, do bận đi làm nhiệm vụ, các học sinh của thầy không rảnh để giải bài toán này, hãy thử giải nó giúp họ nhé.

Input:

• Dòng đầu gồm số nguyên dương ~n~. ~(1 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên miêu tả dãy ~a~. ~(|a_i| \le 10^6)~.

Output:

• Ghi ra một số nguyên miêu tả kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Test

Input:

3
1 2 3

Output:

4

Giải thích:

Ta có ~f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 0 + 1 + 2 + 0 + 1 +0 = 4~.

Cho lưới ô vuông ~n*n~. Các hàng đánh số từ ~1 ... n~ từ trên xuống dưới, các cột đánh số ~1...n~ từ trái sang phải. Ô ở hàng ~i~, cột ~j~ chứa số nguyên ~a_{ij}~ ~(1 \le a_{ij} \le 200)~.

Hãy đếm số hình chữ nhật của lưới có phần tử nhỏ nhất đúng bằng ~100~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. (~1 \le n \le 1000~).

• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên miêu tả lưới ô vuông.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~40\%~ số test có ~n \le 200~.
• ~40\%~ số test có ~n \le 500~.
• ~20\%~ số test có ~n \le 1000~.

Sample Input 1:

3
57 120 87
200 100 150
2 141 135

Sample Output 1:

8