Haskellのリストにおいてk番目の要素を削除する方法が知りたいです

Question

前提

Haskellで競技プログラミングの問題を解いています。

実現したいこと

リストのk番目の要素を削除する素早い方法を教えてもらいたいです。

発生している問題

TLEとなってしまいます。
おそらくリストのk番目の要素を削除する処理（deleteKの部分）で遅くなっていると思うので、このような質問をいたしました。
問題は
https://atcoder.jp/contests/abc125/tasks/abc125_c
です。

該当のソースコード

import Control.Monad
import qualified Data.ByteString.Char8 as BS

main = do
    n <- getLine
    --list <- map read . words <$> getLine
    list <- map (read . BS.unpack).BS.words <$> BS.getLine
    print $ result list


allGCD list  = foldr gcd (head list ) list

deleteK k list = (take k list) ++ (drop (k+1) list )

deleteRe list  =  map (\pair -> deleteK (fst pair) list) ziped
    where ziped = zip [0,1 ..] list


resultList list = map allGCD tmpList
                    where tmpList  = deleteRe list

result list = maximum  $ resultList list

よろしくお願いいたします。

Comments

[actorbug]

遅い原因が deleteK だけではないので、別の方法を探したほうが良いです。

例えば、resultList list の計算量を考えると(tmpList の作成の計算量はとりあえず無視)、
tmpListの各要素が長さ n-1 のリストなので、それぞれの allGCD を求めるのに n-1 回の計算が必要、
tmpList の長さが n なので、ここだけで n * (n-1) で O(n^2)の時間がかかります。

どうしても高速化する方法を思いつかないなら、解説に頼りましょう。
Haskellでやるなら、解説に書いてある累積和を使う方法が良いかと思います。(というかHaskellでセグメントツリーを使う方法を私が知らないので他に選択肢が無かった)
https://blog.hamayanhamayan.com/entry/2019/04/28/085936

[kurokko]

回答していただきありがとうございます！
無事解決いたしました。

Answer 1

以下のようにしたところ無事解決しました。
実行速度が10倍早くなり、なおかつシンプルに書けてとても驚いています。

import Control.Monad
import qualified Data.ByteString.Char8 as BS

main = do
    n <- getLine
    list <- map (read . BS.unpack).BS.words <$> BS.getLine
    print $ result list

result xs = maximum $ zipWith gcd (scanl gcd 0 xs) (tail $ scanr gcd 0 xs) 

ありがとうございました。