Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, a_3, ..., a_N~. Hãy tìm đoạn con liên tiếp và dài nhất mà các phần tử liên tiếp cách đều nhau.

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 độ dài của đoạn con dài nhất thoả mãn đề bài.

Subtasks

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

Sample Test 1

Input

3
1 2 1

Output

3

• Dãy đã cho có các số liên tiếp cách nhau ~1~ đơn vị nên đây là dãy con dài nhất thoả mãn.

Sample Test 2

Input

6
1 2 3 5 7 9

Output

4

Note

• Dãy con liên tiếp dài nhất và cách đều nhau là ~3, 5, 7, 9~. (khoảng cách giữa các số liên tiếp đều là ~2~)

Sample Test 3

Input

6
1 4 7 4 7 1

Output

5

Note

• Dãy con liên tiếp dài nhất và cách đều nhau là ~1, 4, 7, 4, 7~. (khoảng cách giữa các số liên tiếp đều là ~3~)

Xét một dãy ~X~ có ~N~ phần tử ~X_1, X_2, ..., X_N~. Trọng số ~W~ của dãy ~X~ được tính như sau:

Cho dãy ~A~ gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~. Bạn được phép thực hiện thao tác sau tối đa một lần: Chọn một phần tử bất kỳ trong dãy ~A~ rồi đưa phần tử đó lên đầu hoặc xuống cuối dãy ~A~. Tìm trọng số ~W~ lớn nhất có thể của dãy thu được.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^6)~;
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(|A_i| \le 10^6)~.

Output

Một số nguyên là trọng số ~W~ lớn nhất có thể.

Scoring

• Subtask ~1~ ~(20\%)~: ~N = 2~.
• Subtask ~2~ ~(20\%)~: ~N \le 1000~.
• Subtask ~3~ ~(60\%)~: Không có ràng buộc gì thêm.

Ví dụ

Input

4
4 3 2 5

Output

39

Giải thích

Đưa phần tử ~A_3 = 2~ lên đầu, ta được dãy ~\{2, 4, 3, 5\}~.

Trọng số của dãy là: ~W = 2 \times 1 + 4 \times 2 + 3 \times 3 + 5 \times 5 = 39~.

Đây là dãy có trọng số lớn nhất.

Input

4
1 2 3 4

Output

30

Giải thích

Dãy ban đầu đã có trọng số lớn nhất có thể.

Cho một loại cấu trúc dữ liệu dạng tập hợp hỗ trợ hai thao tác sau:

• 1 x: Thêm phần tử x vào tập.
• 2: Bỏ một phần tử ra khỏi tập.

Cấu trúc dữ liệu trên có thể thuộc một trong ba dạng: stack, queue và priority_queue. Cho trước các thao tác và kết quả trả về của thao tác đó, nhiệm vụ của bạn là phân loại cấu trúc dữ liệu trên.

Input

Input gồm nhiều bộ test. Mỗi bộ test gồm:

• Dòng đầu tiên chứa số nguyên dương ~n~ là số lượng thao tác.
• ~n~ dòng sau, mỗi dòng chứa một trong hai thao tác:
  • ~1 \ x~: Thêm ~x~ vào trong tập.
  • ~2 \ x~: Bỏ một phần tử ra khỏi tập, ~x~ là kết quả mà thao tác này trả về.

Input được kết thúc bằng EOF (end-of-file). Input đảm bảo tổng ~n~ trong tất cả các test không quá ~2 \times 10^5~.

Output

• Với mỗi bộ test, in ra trên một kết quả theo cú pháp sau:
  • stack: Nếu cấu trúc dữ liệu ban đầu là stack.
  • queue: Nếu cấu trúc dữ liệu ban đầu là queue.
  • priority_queue: Nếu cấu trúc dữ liệu ban đầu là priority_queue.
  • not sure: Nếu cấu trúc dữ liệu ban đầu có thể là ít nhất hai trong ba cấu trúc dữ liệu trên.
  • impossible: Không cái nào trong ba cấu trúc dữ liệu trên là cấu trúc dữ liệu ban đầu.

Sample Input

3
1 6
2 1
1 1
4
1 4
1 1
2 1
2 4
4
1 1
1 7
2 1
2 7
4
1 8
1 9
1 7
2 9
3
1 1
2 1
1 6

Sample Output

impossible
stack
queue
priority queue
not sure

Bạn có một xâu ~A~ và cần thực hiện các bước sau để mã hóa xâu:

• ~Reverse(A)~: đảo ngược các kí tự trong xâu ~A~. Ví dụ ~Reverse("abc") = "cba"~.
• ~Shuffle(A)~: đổi chỗ các kí tự trong xâu ~A~. Ví dụ, ~Shuffle("god")~ có thể là ~"god", "dog", "dgo", ...~
• ~Merge(A,B)~: Trộn hai xâu ~A,B~ với nhau và giữ nguyên thứ tự của các kí tự trong từng xâu. Ví dụ ~Merge("abc","def")~ có thể là ~"abcdef", "adebcf", ...~

Xâu ~A~ (gồm các kí tự Latin in thường) ban đầu đã được mã hóa thành xâu ~S = Merge(Reverse(A),Shuffle(A))~.

Cho xâu ~S~, hãy xác định xâu ~A~ trước khi mã hóa. Do có thể có nhiều kết quả, hãy in ra xâu ~A~ có thứ tự từ điển nhỏ nhất.

Input

• Gồm một dòng chứa xâu ~S~.

Output

• In ra xâu ~A~ thỏa mãn.

Constraints .

• ~|S| \le 10^5~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): ~n \le 10^5~.

Sample Input 1

abbabb

Sample Output 1

abb

Ta có định nghĩa ~div(i)~ là số lượng ước số của số nguyên dương ~i~. Ví dụ ~div(3) = 2; div(6) = 4~.

Gọi ~S(n,m)~ là tập các số nguyên dương thỏa mãn ~div(i) = n~ và các thừa số nguyên tố của ~i~ đều bé hơn hoặc bằng số nguyên tố thứ ~m~. Ví dụ, ~S(2,3) = \{2,3,5\}~ vì số nguyên tố thứ ~3~ là ~5~.

Bạn hãy in ra số lượng phần tử trong tập ~S(n,m)~. Con số này có thể rất lớn nên hãy in ra theo modulo ~10^9+7~.

Input

• Dòng đầu chứa hai số nguyên dương ~t~ ~(1 \le 2 \times 10^5)~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n,m~ thể hiện truy vấn ~(1 \le n \le 2 \times 10^6, 1 \le m \le 10^9)~.

Output

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

Subtask:

• Subtask ~1~: ~t,n,m \le 10~ ~(30\%)~
• Subtask ~2~: ~t = 1, m \le 10^5~ ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

3
2 3
4 4
3 5

Sample Output 1

3
10
5