Trên bàn có ~n~ viên bi được xếp liên tiếp, viên thứ ~i~ có màu ~c_i~. Với một đoạn liên tiếp các viên bi mà mình chọn, Hiếu sẽ lấy ra tất cả các viên bi mà có màu là duy nhất trong đoạn đó. Hãy tìm cho Hiếu một đoạn liên tiếp sao cho nếu Hiếu chọn đoạn đó thì sẽ lấy ra được nhiều viên bi nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, \ldots, c_n~ ~(1 \le c_i \le n)~.

Output

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

Scoring

• Subtask 1 ~(30\%)~: ~n \le 1000~
• Subtask 2 ~(70\%)~: Không có giới hạn gì thêm.

Sample

Output

8
1 3 1 2 1 5 3 1

Input

4

Cho một cây ~N~ đỉnh, không có trọng số. Định nghĩa ~S(u,r)~ là số lượng đỉnh trong cây con gốc ~u~ khi gốc cây là ~r~. Cho ~Q~ truy vấn: mỗi truy vấn đưa ra hai số nguyên dương ~u,k~ ~(1\leq u,k \leq N)~, yêu cầu tìm giá trị lớn thứ ~k~ của ~S(v,u)~ với ~(1\leq v\leq N)~.

Input

• Dòng ~1~ chứa hai số nguyên dương ~N, Q~. ~(1\leq N, Q \leq 5 \times 10^5)~
• ~N-1~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên dương ~u_i,v_i~ ~(1\leq u_i,v_i\leq N,u_i\neq v_i)~ thể hiện cạnh thứ ~i~ nối trực tiếp giữa hai đỉnh ~u_i,v_i~ trên cây
• ~Q~ dòng tiếp theo, mỗi dòng có hai số nguyên dương ~u,k~ ~(1\leq u,k\leq N)~ cho mỗi truy vấn.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ chứa một số nguyên dương duy nhất là đáp án cho truy vấn thứ ~i~.

Scoring

• Subtask 1 ~(30\%)~: ~N, Q \leq 10^3~.
• Subtask 2 ~(20\%)~: ~u_i=i,v_i=i+1~ với ~1\leq i\leq N-1~.
• Subtask 3 ~(30\%)~: ~N, Q \le 10^5~
• Subtask 4 ~(20\%)~: Không có ràng buộc gì thêm.

Example

Input

8 4
1 2
2 3
2 4
4 5
5 6
5 7
5 8
1 4
5 3
4 8
7 1

Output

4
3
1
8

Note

Ví dụ trong truy vấn ~1~, các giá trị ~S(v,1)~ sau khi được sắp xếp từ lớn đến bé là: ~8,7,5,4,1,1,1,1~, giá trị lớn thứ ~4~ là ~4~ tương ứng với cây con gốc ~5~.

Cho một dãy gồm ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~. Đếm số lượng các đoạn con của dãy này, sao cho tất cả các giá trị xuất hiện trong đoạn con này đều xuất hiện chẵn lần.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng sau chứa ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^9)~.

Output

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

Scoring

• Subtask 1 ~(30\%)~: ~n \le 10^3~
• Subtask 2 ~(30\%)~: ~a_i \le 60~
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample

Input

6
1 2 1 2 2 1

Output

3

Cho ~N~ đoạn thẳng trên trục số, đoạn thứ ~i~ phủ các số trong đoạn ~[l_i, r_i]~ và có độ dài là ~r_i - l_i~. Bạn cần trả lời ~Q~ truy vấn có dạng:

• Cho ba số nguyên ~L, R, K~, đếm số đoạn nằm trong đoạn ~[L, R]~ mà có độ dài không bé hơn ~K~. Nói cách khác, ta cần đếm số ~i~ thỏa mãn ~L \le l_i \lt r_i \le R~ và ~r_i - l_i \ge K~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 5 \times 10^5)~.
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~l_i, r_i~ là đoạn thứ ~i~ ~(1 \le l_i \lt r_i \le N)~.
• ~Q~ dòng sau, mỗi dòng chứa ba số nguyên dương ~L, R, K~ ~(1 \le L \lt R \le N,1 \le K \le N)~ biểu thị một truy vấn.

Output

• Với lần lượt mỗi truy vấn, in ra trên một dòng một số nguyên duy nhất là đáp án của truy vấn đó.

Scoring

• Subtask 1 ~(30\%)~: ~N, Q \le 5000~
• Subtask 2 ~(30\%)~: ~N, Q \le 50000~
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample

Input

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

Output

5
4
3
2
1

Cho ~n~ đoạn ~[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]~. Khôi muốn chọn ra ~m~ đoạn trong số ~n~ đoạn này, với điều kiện cả ~m~ đoạn này phải cùng có ít nhất một điểm chung (tức tồn tại ~x~ sao cho ~l_i \le x \le r_i~ với mọi ~i~ đã chọn).

Với một cách chọn thỏa mãn như vậy, Khôi định nghĩa chi phí của cách chọn đó là chênh lệch giữa độ dài đoạn dài nhất và đoạn ngắn nhất trong số các đoạn đã chọn. Độ dài của một đoạn ~[l, r]~ là ~r - l~. Hãy giúp Khôi tìm chi phí nhỏ nhất trong tất cả các cách chọn thỏa mãn.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~ ~(1 \le m \le n \le 5 \times 10^5)~
• ~n~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~l_i, r_i~ ~(0 \le l_i \le r_i \le 10^9)~ là đoạn thứ ~i~.

Output

• In ra một số nguyên duy nhất là kết quả bài toán. Nếu không có cách chọn nào thỏa mãn thì in ra ~-1~.

Sample

Input 1

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

Output 1

1

Notes: Ta có thể chọn các đoạn ~1, 2, 3~ hoặc ~4, 5, 6~.

Input 2

9 4
2 5
1 7
6 7
1 4
3 5
0 8
1 7
1 2
9 10

Output 2

3

Cho một dãy gồm ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~. Đếm số lượng các đoạn con của dãy này, sao cho tất cả các giá trị xuất hiện trong đoạn con này đều xuất hiện lẻ lần.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng sau chứa ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^9)~.

Output

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

Scoring

• Subtask ~(20\%)~: ~n \le 1000~
• Subtask ~(20\%)~: ~n \le 5 \times 10^4~
• Subtask ~(10\%)~: ~a_i \le 5~
• Subtask ~(20\%)~: ~a_i \le 64~
• Subtask ~(30\%)~: Không có giới hạn gì thêm.

Sample

Input

6
1 2 1 3 1 2

Output

14