Red-Blue Sort
Source: codechef
Difficulty: 1841

Red-Blue Sort
You are given a permutation$^\dagger$$P$of the integers$1$to$N$.
You can perform the following three-step operation on it as many times as you like (possibly, zero):
First, choose any
subset$S$of indices of$P$, whose size is between$1$and$N-1$. (That is,$S$should not be the empty set or the entirety of$\{1, 2, \ldots, N\}$.)
Note that$S$is a subset, so it need not consist of contiguous elements.
Then, paint all the elements at indices of$S$red, and all the elements at indices that are not in$S$blue.
Finally, place all the red elements at indices of$S$in
ascending order
, and blue elements at indices outside$S$in
descending order.
Performing this operation costs
one coin.
For example, suppose$P = [1, 3, 4, 2, 5]$. Suppose you choose the
set of indices$\{2, 4, 5\}$. Then,
Indices$2, 4, 5$are painted red, and indices$1, 3$are painted blue.
Red elements ($P_2 = 3$and$P_4 = 2, P_5 = 5$) are sorted in ascending order at placed at indices$2, 4, 5$, while blue elements ($P_1 = 1, P_3 = 4$) are sorted in descending order and placed at indices$1, 3$.
This turns$P$into$[4, 2, 1, 3, 5]$.
After performing all the operations you wish to perform, you will receive one coin for every index$i$such that$P_i = i$.
What's the
maximum
profit you can earn, if you perform operations optimally?
Here, profit means the number of coins you receive, minus the number of coins you spent on operations.$^\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 a single integer$N$— the size of the permutation.
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 the maximum number of coins you can obtain as profit.
Constraints$1 \leq T \leq 10^5$$2 \leq N \leq 3\cdot 10^5$$1 \leq P_i \leq N$$P_i \neq P_j$for$i \neq j$The sum of$N$over all test cases won't exceed$3\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
We don't need to perform any operation: already$P_1 = 1$and$P_2 = 2$will hold, so we receive two coins and don't pay anything, for a total profit of$2$.
Test case$2$:
It's optimal to not perform any operation, we'll receive$0$coins but also pay$0$, for a net profit of$0$.
Test case$3$:
Choose$S = \{1, 2, 3, 4\}$. Then,
The elements$\{P_1, P_2, P_3, P_4\}$will be placed in ascending order at indices$1, 2, 3, 4$.
The element$P_5$will be placed at index$5$.
The resulting permutation is$P = [1, 2, 3, 4, 5]$.
We receive$5$coins for this, and paid one - so net profit of$5 - 1 = 4$. This is optimal.

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

Sample Output:
2
0
4

C++ solution:
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    if (is_sorted(a.begin(), a.end())) cout << n << "\n";
    else {
      if (n == 2) cout << 0 << "\n";
      else {
        bool ok = false;
        for (int i = 0; i < n; ++i) {
          if (a[i] == i + 1) {
            ok = true;
            break;
          }
        }
        cout << (ok ? n - 1 : n - 2) << "\n";
      }
    }
  }
  return 0; 
}

Go solution:
package main

import (
    "fmt"
)

func shjfre() {
    var djhfjrehfr int64
    fmt.Scan(&djhfjrehfr)
    var jhrugher = make([]int64, djhfjrehfr)
    var rkjgjrhre int64 = 0 // Count of fixed points

    for jhgrejhgre := int64(0); jhgrejhgre < djhfjrehfr; jhgrejhgre++ {
        var kjgjkreg int64
        fmt.Scan(&kjgjkreg)
        jhrugher[jhgrejhgre] = kjgjkreg
        if jhrugher[jhgrejhgre] == jhgrejhgre+1 {
            rkjgjrhre++
        }
    }

    if rkjgjrhre == djhfjrehfr {
        // All elements are fixed
        fmt.Println(djhfjrehfr)
    } else if rkjgjrhre >= 1 {
        // At least one fixed point exists
        // Perform one operation to fix the rest
        fmt.Println(djhfjrehfr - 1)
    } else {
        // No fixed points
        // Maximum profit achievable is N-2
        if djhfjrehfr >= 2 {
            fmt.Println(djhfjrehfr - 2)
        } else {
            // N == 1 (although constraints say N >= 2)
            fmt.Println("0")
        }
    }
}

func main() {
    var rjghrejgr int64
    fmt.Scan(&rjghrejgr)

    for jrhgr := int64(0); jrhgr < rjghrejgr; jrhgr++ {
        shjfre()
    }
}

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

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] a = new int[n];
            String[] inputs = br.readLine().split(" ");
            
            boolean allMatch = true;
            boolean anyMatch = false;

            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(inputs[i]);
                if (a[i] != i + 1) {
                    allMatch = false; // Not all indices match
                } else {
                    anyMatch = true; // At least one index matches
                }
            }

            if (n == 2) {
                // Special case for n == 2
                if (a[0] == 1) {
                    sb.append(2).append("\n"); // Already sorted, profit = 2
                } else {
                    sb.append(0).append("\n"); // Cannot make any coins
                }
            } else {
                if (allMatch) {
                    sb.append(n).append("\n"); // Maximum profit when already sorted
                } else if (anyMatch) {
                    sb.append(n - 1).append("\n"); // Some elements are in correct position
                } else {
                    sb.append(n - 2).append("\n"); // No elements in correct position
                }
            }
        }
        System.out.print(sb);
    }
}

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;
}

let isFirstInLine = true;

function writeInt(value, isLast = false) {
        if (!isFirstInLine) {
                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];
        }
        isFirstInLine = isLast;
        if (isLast) {
                outputBuffer[outputIndex++] = 10;
                isFirstInLine = true;
        }
}

// Template Ends here!

// Solution Function

function solve() {
        let N = readInt();
        let P = [];
        let C = 0;
        for (let i = 0; i < N; i++) {
                P[i] = readInt();
                if (P[i] === i + 1) {
                        C++;
                }
        }
        if (C === N) {
                writeInt(N, true);
        } else if (C >= 1) {
                writeInt(N - 1, true);
        } else {
                if (N >= 2) {
                        writeInt(N - 2, true);
                } else {
                        writeInt(0, 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 = sys.stdin.readline

T = int(input())
out = []
for _ in range(T):
    n = int(input())
    P = list(map(int, input().split()))
    f = 0
    for i, p in enumerate(P, start=1):
        if p == i:
            f += 1
    if f == n:
        out.append(str(n))
    elif f > 0:
        out.append(str(n - 1))
    else:
        out.append(str(n - 2))
print('\n'.join(out))

Ruby solution:
def main
  input = $stdin.read.split
  ptr = 0
  t = input[ptr].to_i
  ptr += 1
  output = []
  
  t.times do
    n = input[ptr].to_i
    ptr += 1
    p = input[ptr, n].map(&:to_i)
    ptr += n
    
    fixed = 0
    p.each_with_index do |val, idx|
      fixed += 1 if val == idx + 1
    end
    
    if fixed == n
      output << n.to_s
    elsif fixed > 0
      output << (n - 1).to_s
    else
      output << (n - 2).to_s
    end
  end
  
  puts output.join("\n")
end

main