class Solution:

    def firstPalindrome(self, words: List[str]) -> str:

        for word in words:

            if word == word[::-1]: return word

        return ""

class Solution:

    def addSpaces(self, s: str, spaces: List[int]) -> str:

        news = s[:spaces[0]]

        for i in range(1, len(spaces)):

            news += " " + s[spaces[i-1]: spaces[i]]

        news += " " + s[spaces[-1]:]

        return news

class Solution:

    def getDescentPeriods(self, prices: List[int]) -> int:

        n = len(prices)

        dp = [1] * n

        for i in range(1, n):

            if prices[i] == prices[i - 1] - 1:

                dp[i] = dp[i - 1] + 1

        return sum(dp)

class Solution:

    def kIncreasing(self, arr: List[int], k: int) -> int:

        n, ans = len(arr), 0

        for off in range(k):

            m, tailsLen = (n - off + k - 1) // k, 0

            tails = [0] * m

            for i in range(m):

                num = arr[off + i * k]

                pos = bisect_right(tails, num, 0, tailsLen)

                tails[pos] = num

                if pos == tailsLen: tailsLen += 1

            ans += m - tailsLen

        return ans

class Solution:

    def kIncreasing(self, arr: List[int], k: int) -> int:

        n, ans = len(arr), 0

        for off in range(k):

            m = (n - off + k - 1) // k

            dp = [1] * m

            for i in range(m):

                for j in range(i):

                    if arr[off + j * k] <= arr[off + i * k]:

                        dp[i] = max(dp[i], dp[j] + 1)

            ans += m - max(dp)

        return ans