Min-Max Game
Source: codechef
Difficulty: 2705

Min-Max Game
Given a permutation$^\dagger$$P$of the integers$1$to$N$, Alice and Bob will play a game on it as follows.
On Alice's turn, she will choose a contiguous subarray of$P$of length
strictly greater
than$1$, and delete the
maximum
element from it.
On Bob's turn, he will choose a contiguous subarray of$P$of length
strictly greater
than$1$, and delete the
minimum
element from it.
After each player's move, the length of the array decreases by$1$.
Alice and Bob take turns moving, with Alice going first. The game ends when$P$has length$1$.
Alice's score is the value of the final element remaining in$P$.
Alice's aim is to maximize her score, while Bob's aim is to minimize Alice's score.
Let$f(P)$denote Alice's score if Alice and Bob play optimally on the permutation$P$.
Alice, wanting to maximize her score as much as possible, decides to cheat a little.
Before the game starts
, she can swap two adjacent elements of$P$as many times as she likes.
Each such swap reduces her final score by$1$.
So, if Alice makes$k$swaps to obtain the permutation$Q$, and the game is played on$Q$, Alice's final score will be$f(Q) - k$.
Find the maximum possible value of Alice's final score.$^\dagger$A permutation of the integers$1$to$N$is an array of length$N$containing each integer from$1$to$N$exactly once. For example, if$N = 3$,$[2, 1, 3]$and$[3, 2, 1]$are permutations, but$[2, 1, 4]$and$[1, 2, 2]$are not.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains one integer$N$, the length of the permutation$P$.
The second line contains$N$space-separated integers$P_1, P_2, \ldots, P_N$.
Output Format
For each test case, output on a new line Alice's maximum possible score.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 5\cdot 10^5$$1 \leq P_i \leq N$$P_i \neq P_j$if$i \neq j$The sum of$N$over all test cases won't exceed$5\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
Only one move can be made - Alice must choose$[1, 2]$and delete its maximum element, to obtain$[1]$. Her score is$1$.
Swapping elements won't change this, so it's best not to swap.
Test case$2$:
Alice can choose the subarray$[2, 1]$on her move and delete$2$. The remaining array is$[1, 3]$. Bob must now choose this and delete the$1$, leaving$[3]$, so Alice obtains a score of$3$. It's optimal to not swap.
Test case$3$:
Alice can first swap the first two elements, to obtain$P = [3, 1, 2]$. This costs one coin.
This is now equivalent to the previous test, so Alice will obtain a score of$3$from the game, making her final score$3 - 1 = 2$.

Sample Input:
4
2
1 2
3
2 1 3
3
1 3 2
4
1 4 3 2

Sample Output:
1
3
2
1

C++ solution:
#include<bits/stdc++.h>
#define int int64_t
#define all(x) (x).begin(), (x).end()
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
using pii = std::pair<int, int>;
using namespace std;


void setIO(string name = "")
{
    cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
    if (name.size())
    {
        freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
// just rng()
mt19937_64 rng(random_device{}());
int MOD = 998244353;
int oo = 1e18;
using namespace std;
const int N = 1e6 + 5;
const int LOG = 22;
int fac[N + 1];
int inv[N + 1];
struct DSU
{
    vector<int> e;
    DSU(int n) {
        e = vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};

int exp(int x, int n, int m) {
    x %= m;
    int res = 1;
    while (n > 0) {
        if (n % 2 == 1) { res = res * x % m; }
        x = x * x % m;
        n /= 2;
    }
    return res;
}

void factorial() {
    fac[0] = 1;
    for (int i = 1; i <= N; i++) { fac[i] = fac[i - 1] * i % MOD; }
}

void inverses() {
    inv[N] = exp(fac[N], MOD - 2, MOD);
    for (int i = N; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }
}

int choose(int n, int r) { 
    if (r > n) return 0;
    if (n < 0) return 0;
    if (r < 0) return 0;
    return (((fac[n] % MOD) * (inv[r] % MOD) % MOD) * (inv[n - r] % MOD)) % MOD; 
}

double dist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool prime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}


struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    int sum(int r) { // [0, r]
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) { // [l, r]
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

void solve() {
    // ifstream cin("Loterija.txt");
    #define test
    #define time1
    #define comb1
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    int res = 0;
    if (n % 2 == 0) {
        int mx = -1;
        int mn = n;
        for (int i = n; i >= 1; --i) {
            mn = min(mn, pos[i]);
            mx = max(mx, pos[i]);
            if (i == n) continue;
            // cout << mn << " " << mx << " " << i << "\n";
            res = max(res, i - mn - (n - 1 - mx));
        }
        cout << res << "\n";
        return;
    }
    for (int i = 0; i < n; ++i) {
        res = max(res, a[i] - min(i, n - i - 1));
    }
    cout << res << "\n";
}   



 






int32_t  main () {
    #ifdef comb
    factorial();
    inverses();
    #endif
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif 
    #ifdef time
    
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    #endif
    setIO(""); int t = 1;
    #ifdef test
    cin >> t;
    #endif
    while (t--) solve();
    #ifdef time
    std::cout << "\n";
    end = std::chrono::system_clock::now();

    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);

    std::cout << "finished computation at " << std::ctime(&end_time)
              << "elapsed time: " << fixed << setprecision(9) << elapsed_seconds.count() << "s\n";
    #endif
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n int
		fmt.Fscan(in, &n)
		p := make([]int, n)
		pi := make([]int, n)
		for i := 0; i < n; i++ {
			fmt.Fscan(in, &p[i])
			pi[p[i]-1] = i
		}

		res := 0
		if n%2 == 1 {
			for i := 0; i < n; i++ {
				val := i + 1 - min(pi[i], n-1-pi[i])
				if val > res {
					res = val
				}
			}
		} else {
			suff := make([]int, n)
			suff[n-1] = pi[n-1]
			for i := n - 2; i >= 0; i-- {
				suff[i] = max(suff[i+1], pi[i])
			}
			pref := make([]int, n)
			pref[n-1] = pi[n-1]
			for i := n - 2; i >= 0; i-- {
				pref[i] = min(pref[i+1], pi[i])
			}
			for i := 0; i < n-1; i++ {
				val := i + 1 - min(pi[i]+n-1-suff[i+1], n-1-pi[i]+pref[i+1])
				if val > res {
					res = val
				}
			}
		}
		fmt.Fprintln(out, res)
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Java solution:
import java.io.*;
import java.util.*;

public class Main implements Runnable {
    private static void solve(MyScanner in, PrintWriter out) {
        int n = in.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) p[i] = in.nextInt();
        if (n % 2 == 1) {
            int max = 0;
            for (int i = 0; i < n; i++) {
                max = Math.max(max, Math.max(p[i] - i, p[i] - (n - 1 - i)));
            }
            out.println(max);
        }
        else if (n == 2) out.println(1);
        else {
            int[] inv = new int[n];
            for (int i = 0; i < n; i++) inv[p[i] - 1] = i;
            int minLeft = inv[n - 1], minRight = n - 1 - inv[n - 1];
            int res = 0;
            for (int i = n - 2; i >= 0; i--) {
                int left = inv[i], right = n - 1 - inv[i];
                res = Math.max(res, i + 1 - Math.min(left + minRight, right + minLeft));
                minLeft = Math.min(minLeft, left);
                minRight = Math.min(minRight, right);
            }
            out.println(res);
        }
    }

    public static void main(String[] args) {
        new Thread(null, new Main(), "Main", 1 << 28).start();
    }

    public void run() {
        MyScanner in = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = in.nextInt();
        for (int i = 1; i <= t; i++) {
            solve(in, out);
        }
        out.close();
    }

    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github :  https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

const inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
const outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

const fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

function readInt() {
        let num = 0,
                sign = 1;
        while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) {
                if (inputBuffer[inputIndex] === 45) sign = -1;
                inputIndex++;
        }
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
                num = num * 10 + (inputBuffer[inputIndex++] - 48);
        }
        return num * sign;
}

function writeInt(value, isLast = false) {
        if (outputIndex > 0) outputBuffer[outputIndex++] = 32;
        if (value < 0) {
                outputBuffer[outputIndex++] = 45;
                value = -value;
        }
        let digits = [];
        do {
                digits.push(value % 10);
                value = Math.floor(value / 10);
        } while (value > 0);
        for (let i = digits.length - 1; i >= 0; i--) {
                outputBuffer[outputIndex++] = 48 + digits[i];
        }
        if (isLast) outputBuffer[outputIndex++] = 10;
}

// Template Ends here!

function b(a, n, x) {
        let l = 0,
                r = n;
        while (l < r) {
                let m = (l + r) >> 1;
                if (a[m][0] < x) l = m + 1;
                else r = m;
        }
        return r;
}

function solve() {
        let n = readInt();
        let a = Array.from({
                length: n
        }, () => readInt());
        if (n % 2) {
                let ans = 1;
                for (let i = 0; i < n; i++) ans = Math.max(ans, a[i] - Math.min(i, n - 1 - i));
                writeInt(ans, true);
                return;
        }
        let l = [],
                r = [];
        for (let i = 0; i < n; i++) {
                l.push([a[i], i]);
                r.push([a[i], n - 1 - i]);
        }
        l.sort((x, y) => x[0] - y[0]);
        r.sort((x, y) => x[0] - y[0]);
        for (let i = n - 2; i >= 0; i--) {
                l[i][1] = Math.min(l[i][1], l[i + 1][1]);
                r[i][1] = Math.min(r[i][1], r[i + 1][1]);
        }
        let ans = 1;
        for (let i = 0; i < n; i++) {
                let j = b(r, n, a[i]);
                if (j !== n) ans = Math.max(ans, a[i] - i - r[j][1]);
                j = b(l, n, a[i]);
                if (j !== n) ans = Math.max(ans, a[i] - (n - 1 - i) - l[j][1]);
        }
        writeInt(ans, true);
}

let t = readInt();
while (t--) solve();
fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
# cook your dish here
import sys

input = lambda: sys.stdin.readline().rstrip()

t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    pi = [None] * n
    for i in range(n):
        pi[p[i] - 1] = i
    res = 0
    if n % 2 == 1:
        for i in range(n):
            res = max(res, i + 1 - min(pi[i], n - 1 - pi[i]))
    else:
        suff = [None] * n
        suff[n - 1] = pi[n - 1]
        for i in range(n - 2, -1, -1):
            suff[i] = max(suff[i + 1], pi[i])
        pref = [None] * n
        pref[n - 1] = pi[n - 1]
        for i in range(n - 2, -1, -1):
            pref[i] = min(pref[i + 1], pi[i])
        for i in range(n - 1):
            res = max(res, i + 1 - min(pi[i] + n - 1 - suff[i + 1], n - 1 - pi[i] + pref[i + 1]))
    print(res)

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  t = input[ptr].to_i
  ptr += 1
  results = []
  t.times do
    n = input[ptr].to_i
    ptr += 1
    p = input[ptr, n].map(&:to_i)
    ptr += n
    pi = Array.new(n)
    (0...n).each do |i|
      pi[p[i] - 1] = i
    end
    res = 0
    if n % 2 == 1
      (0...n).each do |i|
        res = [res, i + 1 - [pi[i], n - 1 - pi[i]].min].max
      end
    else
      suff = Array.new(n)
      suff[n - 1] = pi[n - 1]
      (n - 2).downto(0) do |i|
        suff[i] = [suff[i + 1], pi[i]].max
      end
      pref = Array.new(n)
      pref[n - 1] = pi[n - 1]
      (n - 2).downto(0) do |i|
        pref[i] = [pref[i + 1], pi[i]].min
      end
      (0...n - 1).each do |i|
        term1 = pi[i] + n - 1 - suff[i + 1]
        term2 = n - 1 - pi[i] + pref[i + 1]
        res = [res, i + 1 - [term1, term2].min].max
      end
    end
    results << res
  end
  puts results.join("\n")
end

solve