阿里巴巴3.30号笔试，第二题

import java.text.DecimalFormat;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[][] arr1 = new int[n][n];
        for (int i = n - 1; i  >= 0; i--) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j >= 0; j--) {
                if (max < arr[j]) {
                    arr1[n - 1 - i][j] = arr[j];
                    max = arr[j];
                } else {
                    arr1[n - 1 - i][j] = max;
                }

            }
        }
        double a = (n + 1) * n / 2;
        double b = 0;


        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                b += arr1[n - 1 - i][j];
            }


        }

        double res = b / a;
        DecimalFormat df = new DecimalFormat("#0.000000");
        System.out.println(df.format(res));

    }

}