package main import ( "bufio" "fmt" "os" "strconv" ) func getScanner(fp *os.File) *bufio.Scanner { scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 500001), 500000) return scanner } func getNextString(scanner *bufio.Scanner) string { scanner.Scan() return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextUint64(scanner *bufio.Scanner) uint64 { i, _ := strconv.ParseUint(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout if len(os.Args) > 1 { fp, _ = os.Open(os.Args[1]) if len(os.Args) > 2 { wfp, _ = os.Create(os.Args[2]) } } scanner := getScanner(fp) writer := bufio.NewWriter(wfp) n := getNextInt(scanner) aa := make([]alias, n) for i := 0; i < n; i++ { aa[i] = alias(getNextInt64(scanner) + int64(1e9)) } wl := WaveletKeanuReeves{} wl.init(aa) var ans alias for k := 1; k <= n; k++ { sum := make([]alias, n/k) for s := 0; s+k < n; s += k { i := s / k sum[i] = wl.quantile(s, s+k, k/2+1) - alias(1e9) if s == 0 { continue } sum[i] += sum[i-1] } for i := 1; i < n/k; i++ { if sum[i] < sum[i-1] { sum[i] = sum[i-1] } } if ans < sum[n/k-1]*alias(k) { ans = sum[n/k-1] * alias(k) } for t := n; t-k >= 0; t -= k { i := t/k - 1 sum[i] = wl.quantile(t-k, t, k/2+1) - alias(1e9) if i+1 < n/k { sum[i] += sum[i+1] } if i-1 >= 0 { if ans < (sum[i]+sum[i-1])*alias(k) { ans = (sum[i] + sum[i-1]) * alias(k) } } else { if ans < sum[i]*alias(k) { ans = sum[i] * alias(k) } } } } fmt.Fprintln(writer, ans) writer.Flush() } type alias int64 // WaveletKeanuReeves ... type WaveletKeanuReeves struct { bits, n int tree [][]int data, topIndex []int } func (wl *WaveletKeanuReeves) init(raw []alias) { n := len(raw) wl.bits = 62 wl.tree = make([][]int, wl.bits, wl.bits) wl.data = make([]int, wl.bits*(n+1), wl.bits*(n+1)) buf := make([]int, n, n) sorted := make([]int, n, n) wl.topIndex = make([]int, n, n) for i := 0; i < n; i++ { sorted[i] = i wl.topIndex[i] = -1 } for i := wl.bits - 1; i >= 0; i-- { wl.tree[i] = wl.data[i*(n+1) : (i+1)*(n+1)] bi := 0 si := 0 for ii := 0; ii < n; ii++ { wl.tree[i][ii+1] = int(raw[sorted[ii]] >> uint(i) & 1) if wl.tree[i][ii+1] == 0 { sorted[si] = sorted[ii] si++ } else { buf[bi] = sorted[ii] bi++ } wl.tree[i][ii+1] += wl.tree[i][ii] } for ii := 0; ii < bi; ii++ { sorted[si+ii] = buf[ii] } } wl.n = n } func (wl *WaveletKeanuReeves) count0(h, i int) int { return i - wl.tree[h][i] } func (wl *WaveletKeanuReeves) count1(h, i int) int { return wl.tree[h][i] } func (wl *WaveletKeanuReeves) next(h, i int) int { bit := wl.tree[h][i+1] - wl.tree[h][i] if bit == 0 { return wl.count0(h, i) } index := wl.count0(h, wl.n) + wl.tree[h][i] return index } func (wl *WaveletKeanuReeves) nextrange0(h, l, r int) (int, int) { return wl.count0(h, l), wl.count0(h, r) } func (wl *WaveletKeanuReeves) nextrange1(h, l, r int) (int, int) { start1 := wl.count0(h, wl.n) return start1 + wl.count1(h, l), start1 + wl.count1(h, r) } func (wl *WaveletKeanuReeves) access(at int) alias { var ans alias for i := wl.bits - 1; i >= 0; i-- { bit := alias(wl.tree[i][at+1] - wl.tree[i][at]) ans |= bit << uint(i) at = wl.next(i, at) } return ans } func (wl *WaveletKeanuReeves) rank(at int, c alias) int { l := 0 r := at for i := wl.bits - 1; i >= 0 && l < r; i-- { bit := int(c >> uint(i) & 1) if bit == 0 { l, r = wl.nextrange0(i, l, r) continue } l, r = wl.nextrange1(i, l, r) } return r - l } func (wl *WaveletKeanuReeves) rank0(h, at int) int { l := 0 r := wl.n for l < r { m := (l + r) >> 1 if wl.count0(h, m) < at+1 { l = m + 1 continue } r = m } return l - 1 } func (wl *WaveletKeanuReeves) rank1(h, at int) int { l := 0 r := wl.n for l < r { m := (l + r) >> 1 if wl.count1(h, m) < at+1 { l = m + 1 continue } r = m } return l - 1 } func (wl *WaveletKeanuReeves) gotop(h, index int) int { for i := h; i < wl.bits; i++ { index1 := wl.count0(i, wl.n) if index < index1 { index = wl.rank0(i, index) continue } index = wl.rank1(i, index-index1) } return index } func (wl *WaveletKeanuReeves) gettopindex(index int) int { if wl.topIndex[index] != -1 { return wl.topIndex[index] } wl.topIndex[index] = wl.gotop(0, index) return wl.topIndex[index] } func (wl *WaveletKeanuReeves) selects(at int, c alias) int { l := 0 r := wl.n for i := wl.bits - 1; i >= 0 && l < r; i-- { bit := int(c >> uint(i) & 1) if bit == 0 { l, r = wl.nextrange0(i, l, r) continue } l, r = wl.nextrange1(i, l, r) } return wl.gettopindex(l + at) } func (wl *WaveletKeanuReeves) getbottomrange(l, r int, c alias) (int, int) { for i := wl.bits - 1; i >= 0; i-- { bit := int(c >> uint(i) & 1) if bit == 0 { l, r = wl.nextrange0(i, l, r) continue } l, r = wl.nextrange1(i, l, r) } return l, r } func (wl *WaveletKeanuReeves) quantile(l, r, rank int) alias { if rank > r-l { return -1 } var ans alias for i := wl.bits - 1; i >= 0; i-- { c1 := wl.count1(i, r) - wl.count1(i, l) if c1 >= rank { ans |= 1 << uint(i) l, r = wl.nextrange1(i, l, r) continue } l, r = wl.nextrange0(i, l, r) rank -= c1 } return ans } func (wl *WaveletKeanuReeves) rangerankless(l, r int, c alias) int { ans := 0 for i := wl.bits - 1; i >= 0; i-- { bit := int(c >> uint(i) & 1) if bit == 0 { l, r = wl.nextrange0(i, l, r) continue } ans += wl.count0(i, r) - wl.count0(i, l) l, r = wl.nextrange1(i, l, r) } return ans } func (wl *WaveletKeanuReeves) rangerankmore(l, r int, c alias) int { ans := 0 for i := wl.bits - 1; i >= 0; i-- { bit := int(c >> uint(i) & 1) if bit == 1 { l, r = wl.nextrange1(i, l, r) continue } ans += wl.count1(i, r) - wl.count1(i, l) l, r = wl.nextrange0(i, l, r) } return ans } func (wl *WaveletKeanuReeves) rangefreq(l, r int, min, max alias) int { return wl.rangerankless(l, r, max) - wl.rangerankless(l, r, min) } func (wl *WaveletKeanuReeves) prevless(at int, c alias) int { l := 0 r := at for l < r { m := (l + r) >> 1 if wl.rangerankless(m, at, c) == 0 { r = m continue } l = m + 1 } return l - 1 } func (wl *WaveletKeanuReeves) prevmore(at int, c alias) int { l := 0 r := at for l < r { m := (l + r) >> 1 if wl.rangerankmore(m, at, c) == 0 { r = m continue } l = m + 1 } return l - 1 } func (wl *WaveletKeanuReeves) nextless(at int, c alias) int { l := at + 1 r := wl.n for l < r { m := (l + r) >> 1 if wl.rangerankless(at+1, m+1, c) == 0 { l = m + 1 continue } r = m } return r } func (wl *WaveletKeanuReeves) nextmore(at int, c alias) int { l := at + 1 r := wl.n for l < r { m := (l + r) >> 1 if wl.rangerankmore(at+1, m+1, c) == 0 { l = m + 1 continue } r = m } return r }