Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

9
1 3 -1 3 -2 4 -5 -6 7

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

9
1 3 -1 3 -2 4 -5 6 7

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, \dots, A_N~. Vị trí ~i~ (~1 \leq i \leq N~) được gọi là vị trí cân bằng của dãy khi ~H = |(A_1 + A_2 + \dots + A_i) - (A_{i + 1} + \dots + A_N)|~ đạt giá trị bé nhất.

Hãy tìm giá trị ~H~ bé nhất thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq n \leq 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_n~ (~A_i \leq 10^9~).

Output

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

Sample Tests

Note

• Có thể chọn vị trí cân bằng ~i = 3~, khi đó ~H = |(1 + 1 + 3) - (6 + 2)| = 3~.

Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, a_3, ..., a_N~. Hãy tìm một đoạn con liên tiếp trong dãy sao cho chúng có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, a_3, ... a_N~. (~|a_i| \leq 10^9~)

Output

• In ra tổng lớn nhất tìm được.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 100~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 4 (~30\%~ số điểm): ~N \leq 10^6~.

Sample Test

Input

7
-2 -3 4 -1 -2 1 5

Output

7

Note

• Đoạn con có tổng lớn nhất là ~4, -1, -2, 1, 5~.

Cho một chuỗi kí tự gồm các kí tự chữ viết hoa, có bao nhiêu cách chọn ra bộ kí tự AMS khác nhau. Các kí tự được chọn phải để theo thứ tự trước sau như ban đầu.

Ví dụ, với câu CHAO AMS có ~2~ bộ kí tự AMS, tính theo vị trí là ~(3, 7, 8)~ và ~(6, 7, 8)~.

Input

Nhập vào một xâu văn bản ~S~ có tối đa ~10^6~ kí tự. Các kí tự đều là chữ in hoa.

Output

Ghi ra số cách chọn bộ kí tự AMS.

Ví dụ

Input

CHAO AMS

Output

2

Input

AMSER IN AMS

Output

4

Sau thành công từ quán cà phê nổi tiếng của mình, TDZ quyết định tự thưởng cho bản thân.

Ở cửa hàng có trưng bày ~n~ món hàng, món thứ ~i~ có giá ~v_i~. Với tổng số tiền ~x~ trong tay, TDZ muốn mua 2 món quà khác nhau có tổng giá trị lớn nhất và tất nhiên không vượt quá khả năng chi trả của mình. TDZ đang loay hoay không biết phải chọn món nào, bạn hãy giúp TDZ nhé.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ và ~x~ lần lượt là số món hàng và số tiền TDZ sở hữu (~2 \leq n \leq 10^5, x \leq 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~v_1, v_2, v_3, \ldots, v_n~ tương ứng với giá tiền từng món hàng (~v_i \leq 10^9~).

Output

In ra số tiền cần trả, hoặc 0 nếu TDZ không thể chọn được ~2~ món thoả mãn.

Subtasks

• Subtask 1 (~50\%~): ~n \leq 10^3~.
• Subtask 2 (~50\%~): Không có điều kiện gì thêm.

Sample Test

Input:

6 18
5 3 10 2 4 9

Output:

15

Note: Ở ví dụ trên TDZ sẽ chọn món thứ nhất và thứ ba. Tổng số tiền cần chi sẽ là ~5 + 10 = 15~.

Mít có các que tính có nhiều độ dài và màu sắc. Hôm nay học về hình tam giác nhọn, Mít đã nghĩ ra một bài toán rất độc đáo có liên quan tới tam giác nhọn và các que tính của mình. Mít chia các que tính thành ~N~ bộ, các que tính trong cùng một bộ thì có độ dài bằng nhau nhưng có màu khác nhau. Độ dài của các que tính trong hai bộ bất kì là khác nhau. Mít đố các bạn đếm xem có bao nhiêu tam giác nhọn khác nhau có thể được tạo ra từ ~N~ bộ que tính đó. Chú ý: mỗi cạnh của tam giác được chọn từ một bộ que tính khác nhau tức là sẽ không có tam giác cân và hai tam giác nhọn được gọi là giống nhau khi các cặp cạnh tương ứng bằng nhau và cùng màu, ngược lại là khác nhau.

Yêu cầu: Cho độ dài và số lượng các que tính của ~N~ bộ que tính, hãy lập trình đếm số lượng tam giác nhọn khác nhau có thể tạo ra.

Dữ liệu vào từ tệp văn bản TRIACU.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 2000)~ là số bộ que tính;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, C~ mô tả độ dài và số lượng que tính của bộ thứ ~i~ ~(1 ≤ i ≤ N~; ~\ L ≤ 10^6~; ~\ C ≤ 10^3)~.

Kết quả ghi ra tệp văn bản TRIACU.OUT:

Một số nguyên duy nhất là số lượng tam giác nhọn khác nhau.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 200~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

4
3 3
4 1
5 2
6 2

Output

4

Giải thích

Có ~4~ tam giác nhọn có thể tạo ra từ bộ que tính thứ ~2, 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

Cho dãy ~a~ gồm ~n~ phần tử và một số nguyên dương ~k~. Hãy tìm đoạn ~a[l..r]~ có độ dài tối thiểu là ~k~ sao cho ~med(l, r)~ đạt giá trị lớn nhất. Biết rằng: ~med(l, r)~ là phần tử trung vị sau khi sắp xếp đoạn ~a[l..r]~ theo thứ tự không giảm, phần tử trung vị của một dãy có độ dài ~n~ là phần tử ở vị trí thứ ~\lfloor \frac{n+1}{2} \rfloor~ của dãy đó.

Ví dụ: Với ~A = \{3, 1, 4, 1, 5, 1, 2, 1, 2\}~, ~med(1, 5) = 3; \ med(6, 9) = 1~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le k \le n \le 10^5)~;
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le n; \ 1 \le i \le n)~.

Output

In ra một số nguyên là giá trị lớn nhất của ~med(l, r)~ thoả mãn đề bài.

Examples

Input

4 2
1 3 4 2

Output

3

Giải thích

Chọn ~l=2, r=4~. Khi đó, ~med(2, 4) = 3~.

Cho một dãy ngoặc ~s~ là một dãy ngoặc đúng, phần tử thứ ~i~ là ~s_i~ có thể bằng ~'('~ hoặc ~')'~.

Bạn cần trả lời ~q~ truy vấn, truy vấn ~i~ có dạng: ~l_i, r_i~, nhiệm vụ của bạn là kiểm tra xem dãy ~[l_i, r_i]~ có tạo thành một dãy ngoặc đúng hay không. Nếu ~[l_i, r_i]~ tạo thành một dãy ngoặc đúng, in ra YES, ngược lại in ra NO.

Dãy ngoặc là một dãy chỉ gồm các kí tự ( hoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

• Dãy ngoặc rỗng là một dãy ngoặc đúng.
• Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ là một dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng.

Ví dụ: (()), ()()(), ()(()) là các dãy ngoặc đúng, còn (, ), ()(((() thì không.

Input

• Dòng đầu gồm một xâu kí tự miêu tả dãy ~s~.
• Dòng thứ hai gồm một số nguyên dương ~q~ miêu tả số truy vấn.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~l_i, r_i~ miêu tả dãy ngoặc con cần kiểm tra.

Constraints

• ~|s| \leq 10^6, \ q \leq 10^5~
• ~1 \leq l_i, r_i \leq |s|, \ \forall i = 1 ... q~

Subtask

• Subtask ~1~ ~(10 \%)~: ~r_i - l_i = 1~, tức dãy ~[l_i, r_i]~ chỉ gồm 2 kí tự.
• Subtask ~2~ ~(40 \%)~: ~|s|, q \leq 1000~.
• Subtask ~3~ ~(25 \%)~: ~|s|, q \leq 10^5~.
• Subtask ~4~ ~(25 \%)~: Không có giới hạn gì thêm.

Examples

Input

()()()
2
1 5
1 2

Output

NO
YES

Input

()()()(())
4
5 8
5 10
1 6
2 8

Output

NO
YES
YES
NO

Khôi có một dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một dãy con ~a_l, a_{l + 1}, \dots, a_{r}~ được gọi là pro nếu

• ~a_i + 1 = a_{i + 1},\ \forall l \le i \lt r~.

Ví dụ ~a = [1, 3, 4, 5, 2]~, thì dãy con ~[3, 4, 5]~ là dãy pro, dãy con ~[3]~ là dãy pro, nhưng dãy ~[3, 4, 5, 2]~ thì không. Chú ý dãy con có một phần tử cũng được gọi là pro.

Khôi định nghĩa độ pro của dãy ~a~ là dãy con dài nhất của ~a~ mà là dãy pro. Trong ví dụ trên, độ pro của dãy ~a = [1, 3, 4, 5, 2]~ là ~3~.

Để làm cho dãy số của mình trở nên pro nhất có thể, Khôi sẽ thực hiện tối đa ~k~ lần chỉnh sửa, mỗi lần chọn một vị trí ~i~, và tăng hoặc giảm ~a_i~ đi ~1~ đơn vị. Trong tất cả các cách chỉnh sửa có thể, Khôi muốn chọn ra cách có độ pro lớn nhất. Vì Khôi khá ga` nên hãy giúp Khôi tìm ra độ pro có thể này nhé!

Input (vào từ file văn bản proseq.inp)

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 \le n \le 5 \times 10^5,\ 0 \le k \le 10^{15})~.
• Dòng sau chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9)~.

Output (ghi ra file văn bản proseq.out)

• In ra một sô nguyên duy nhất là độ pro lớn nhất có thể sau khi thực hiện tối đa ~k~ lần chỉnh sửa.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~k = 0~.
• Subtask 2 (~20\%~ số điểm): ~n \le 500~.
• Subtask 3 (~30\%~ số điểm): ~n \le 5000~
• Subtask 4 (~30\%~ số điểm): Không có điều kiện gì thêm.

Sample Input 1

5 0
1 3 4 2 5

Sample Output 1

2

Notes: Ta không thể thực hiện bước chỉnh sửa nào, nên dãy ~a~ giữ nguyên và có độ pro là ~2~.

Sample Input 2

6 5
2 0 3 3 6 8

Sample Output 2

5

Notes: Ta có thể biến dãy ~a~ về ~[1, 2, 3, 4, 5, 8]~ và có độ pro là ~5~.