Pagination: Last Page Missing

I’ve about 12 records and that means I should have 4 pages. My best attempt so far at getting pagination to work is this, and I’d really appreciate if someone could tell me where exactly am I going wrong?

    <div id="main-content">
    <div class="container">

        <?php

            $paged = ( get_query_var('paged') ) ? get_query_var('paged') : 1;
            $args = array(
                'post_type' => 'job',
                'posts_per_page' => 3,
                'paged' => $paged
            );
            $query = new WP_Query( $args );
            while ( $query->have_posts()): $query->the_post();
                <h1> <?php the_title(); ?> </h1>
                <p> <?php  the_excerpt(); ?> </p>
                <?php
            endwhile; ?>

    </div> <!-- .container -->
</div> <!-- #main-content -->

<!-- Start Navigation Here -->
<?php
    global $wp_query;

    $total_pages    =   $wp_query->max_num_pages;

    if ($total_pages > 1) {

        $current_page = max( 1, get_query_var('paged'));
        echo '<div class="page_nav">';
        echo paginate_links(array(
            'base' => get_pagenum_link(1) . '%_%',
            'format' => '/page/%#%',
            'current' => $current_page,
            'total' => $total_pages,
            'prev_text' => 'Prev',
            'next_text' => 'Next'
        ));
        echo '</div>';
    }
?>

<?php wp_reset_postdata(); ?>

UPDATED CODE:

Okay this is much simplified, but this continues to show 5 pages irrespective of how many ‘posts_per_page’ count I set. With total of 24 records, I am expecting only 2 pages (aka max_num_pages), but I keep getting ‘5’. Here’s my simplified, latest code:

        //Generate the loop here

        //Prepare arguments for WP_QUERY
        $paged = ( get_query_var('paged') ) ? get_query_var('paged') : 1;
        $args   = array(

            'posts_per_page'    => 12,
            'post_type'         => 'job',
            'paged'             => $paged

        );

    $query  = new WP_Query( $args );

    if ($query->have_posts()) {

        while ( $query->have_posts()) {
            $query->the_post();
            ?> <li><?php the_title(); ?></li> <?php
        }
    } else {
        echo "<h2>No Jobs Found</h2>";
    }
    // Pagination begins here
    $paginateArgs = array(
        'base'  => '%_%',
        'format' => '?paged=%#%',
        'current'   => $paged
    );
    echo paginate_links( $paginateArgs );
    wp_reset_postdata();
    ?>