Dãy số và trung vị

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử.

Với mỗi đoạn con \(A[l..r]\) (\(1 \le l \le r \le n\)), ta định nghĩa:

• \(W(l,r,x)\) là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\dots,A[r]\).

• Gọi \(B\) là dãy gồm các phần tử đoạn \(A[l..r]\), và sắp xếp \(B\) tăng dần được dãy \(C\).

  Tập trung vị của đoạn là:
  $
  S(l,r) = { C[\lfloor (k-1)/2 \rfloor],\; C[\lceil (k-1)/2 \rceil] },
  $
  trong đó \(k = r-l+1\).

Giá trị của đoạn \((l,r)\) được định nghĩa là:
$
\max_{x \in S(l,r)} W(l,r,x).
$

Lưu ý: tập \(S(l,r)\) sẽ chứa phần tử trung vị duy nhất nếu đoạn có số phần tử lẻ, và chứa hai phần tử trung vị nếu đoạn có số phần tử chẵn.

Yêu cầu: Tìm giá trị lớn nhất trong tất cả các đoạn \((l,r)\).

\InputFile

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le n\)).

\OutputFile

In ra một số nguyên duy nhất --- giá trị lớn nhất có thể đạt được.

\Scoring

• \(11\) điểm: \(n \le 100\).
• \(17\) điểm: \(n \le 2 \times 10^3\).
• \(7\) điểm: tồn tại \(x\) sao cho dãy tăng đến \(x\) rồi giảm sau đó.
• \(12\) điểm: \(A_i \le 3\).
• \(13\) điểm: mỗi giá trị xuất hiện nhiều nhất 2 lần.
• \(22\) điểm: \(n \le 8 \times 10^4\).
• \(18\) điểm: không có ràng buộc thêm.

Example

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2