SMITH, Circuit Judge.
Marlin Hawk Wing pleaded guilty to larceny in violation of 18 U.S.C. §§ 661 and 1153. The district court1 sentenced Hawk Wing to 18 months in prison, 2 years of supervised release, $1,747.36 in restitution, and a $100 assessment to the Victims’ Assistance Fund. For the reasons discussed below, we affirm.
I. Background
Hawk Wing pleaded guilty to stealing construction equipment from the Oglala Sioux Tribal Authority. After his plea, a presentence report (“PSR”) was prepared that assigned Hawk Wing six criminal history points based upon five prior offenses.2 Although the PSR recommended no “Chapter Four Enhancements,” the “Aggravating and/or Mitigating Circumstances,” section stated that “[t]he defendant has an extensive criminal history for [625] which no criminal history points were assigned.” Hawk Wing accepted responsibility resulting in an adjusted offense level of four. Hawk Wing’s Guidelines range calculation was zero to six months. Pending sentencing, Hawk Wing was incarcerated at the Pennington and Meade County jails. Hawk Wing committed two rule infractions during his time at those facilities.
At sentencing, the government, consistent with the plea agreement, recommended that the district court reduce Hawk Wing’s offense level by two levels and that the district court sentence him at the low end of the appropriate Guidelines range. The district court, however, denied Hawk Wing the two-level downward adjustment for acceptance of responsibility based on his two rule infractions at the Pennington and Meade County jails. The district court then proceeded to consider the adequacy of Hawk Wing’s criminal history and the 18 U.S.C. § 3553(a) factors.
The district court determined that Hawk Wing’s criminal history score did not adequately reflect his record because the PSR did not assign any criminal history points for Hawk Wing’s juvenile adjudications, seven additional adult criminal convictions, and “other criminal conduct.” “Other criminal conduct” included Hawk Wing’s arrest for having an open container for which he pleaded guilty; his arrest for consuming alcohol in a public place for which he pleaded guilty; his four active warrants for failing to appear stemming from three arrests; his arrest for tampering with a motor vehicle for which court information is unknown; and his arrest for third-degree burglary for which the charge against him was later dismissed. Based on Hawk Wing’s conduct for which the PSR assigned no criminal history points, the district court increased his criminal history points from six to seven, which placed him in a Category IV and correlated to a sentence of six to twelve months of incarceration.
The district court then addressed whether an upward departure would be reasonable. The district court stated, “[wjhile the Court recognizes that the guidelines are not mandatory, the Court addresses the issue of a departure upward which would be evaluated from the standpoint of reasonableness.” The district court recognized that United States v. Haack, 403 F.3d 997 (8th Cir.2005), outlines the procedure district courts should follow in determining a proper sentence. Applying the procedure in Haack, the district court considered the § 3553(a) factors, stating its basis for its upward departure as follows:
The Court, in determining the particular sentence to be imposed shall consider, one, the nature and circumstances of the offense and the history and characteristics of the defendant. In that connection, the Court notes that the charge, which in this case was larceny, involved essentially the theft of various tools and personal property, not high in value but approximately $1,700 in value. The Court has set forth specifically the history and characteristics of this defendant and that history and characteristics] speak for itself.
In considering the need for the sentence imposed under [§ ] 3553(a)(2), the Court considers the seriousness of the offense to promote respect for the law and to provide just punishment for the offense, to afford adequate deterrence to criminal conduct. The Court is of the abiding feeling that the defendant, by reason of his past history, cannot be deterred from further criminal conduct. By the defendant’s own admission he is an alcoholic and incarceration is reflected by the Court’s sentence and will assist with providing him with needed education or vocational training, medical care, or oth[626] er corrections treatment in the most effective manner.
The district court then sentenced Hawk Wing to a “non-guideline” sentence of 18 months’ imprisonment. Hawk Wing filed a timely notice of appeal.
II. Analysis
Hawk Wing raises five arguments on appeal: (1) that the district court failed to provide him with reasonable notice of the upward departure; (2) that the district court erroneously relied on Hawk Wing’s prior arrests in determining whether to depart upwards; (3) that the district court utilized incarceration to provide rehabilitative services; (4) that the district court’s finding that Hawk Wing’s criminal history required placement in a criminal history Category IV rather than a Category III precluded any further upward departure based upon the inadequacy of his criminal history; and (5) that the district court failed to impose a reasonable sentence.
A. Notice of Departure
Hawk Wing first argues that the district court failed to give the parties reasonable advance notice of its intention to depart from the Sentencing Guidelines pursuant to Federal Rules of Criminal Procedure 32(h).3 Hawk Wing supports his contention based on the PSR’s failure to explicitly recommend a departure or identify any Guidelines provision for a departure and specifically concluded there were no “Chapter Four Enhancements.” In response, the government asserts that the district court gave Hawk Wing reasonable notice of departure because the PSR stated, under the heading “Aggravating or Mitigating Circumstances,” that “the defendant has an extensive criminal history for which no criminal history points were assigned.” Because Hawk Wing failed to raise his lack of notice argument during the sentencing hearing, we must review the adequacy of notice issue for plain error. United States v. Sample, 213 F.3d 1029, 1031 (8th Cir.2000).
A district court must give notice to the parties of its intent to make a sua sponte departure from the Sentencing Guidelines. Burns v. United States, 501 U.S. 129, 111 S.Ct. 2182, 115 L.Ed.2d 123 (1991). In Bums, the PSR specifically stated that there were “no factors that would warrant a departure from the guideline sentence.” Id. at 131, 111 S.Ct. 2182. Nevertheless, the district court announced at the end of sentencing that it was departing from the Sentencing Guidelines range without previously giving the parties advance notice of its intent to depart. Id. In reversing the court of appeal’s affirmance of the district court’s departure, the Court held that Rule 32 required that the district court “give the parties reasonable notice that it is contemplating [a departure]” before it can “depart upward on a ground not identified as a ground for upward departure either in the presentence report or in a prehearing submission by the Government.” Id. at 138-39, 111 S.Ct. 2182 (emphasis added).
In cases following Bums, we have addressed when the district court must provide formal notice to the parties of its intent to depart upward. In United States v. Andrews, 948 F.2d 448 (8th Cir.1991), the PSR “identified two factors that might [627] warrant an upward departure.” Id. at 449. Recognizing that the PSR “expressly noted the presence of factors which might warrant departure,” this court held that the district court did not have to give formal notice of its intent to depart. Id. In addition to Andrews, this court has found that grounds for a departure existed where the PSR included a section entitled “Factors That May Warrant Departure,” which listed specific factors that could justify an upward departure. United States v. Beatty, 9 F.3d 686, 688 (8th Cir.1993). Similarly, when a PSR indicates that the defendant’s convictions could support an upward departure, this court has held that “[n]o other form of notice is required if the grounds for an upward departure are identified in the PSR.” United States v. Drapeau, 110 F.3d 618 (8th Cir.1997); see also Sample, 213 F.3d at 1029 (involving a PSR that indicated an upward departure may be warranted).
Thus, when notice of departure is “sufficiently provided” in the PSR, the district court is not required to give the parties notice of upward departure. United States v. Hill, 951 F.2d 867, 867 (8th Cir. 1991). Even if the PSR does not affirmatively recommend an upward departure, if it includes “specific grounds that may form the basis for an upward departure,” then Rule 32’s notice requirement is satisfied. Sample, 213 F.3d at 1031-32 (holding that because the “district court’s departure decision directly correlate^] with the PSR’s plain language,” the defendant received adequate notice). Only when the “ground for upward departure is not identified in ‘the presentence report or in a prehearing submission by the government’ ” must the district court itself provide advance notice. Id. (quoting Burns, 501 U.S. at 138, 111 S.Ct. 2182). When the district court is required to give notice, it must give such notice before the sentencing hearing. United States v. LeCompte, 99 F.3d 274, 280 (8th Cir.1996).
In contrast to the preceding cases, we have held that where a PSR “explicitly stated” that there were no factors warranting an upward departure, the defendant failed to receive proper notice. United States v. Johnson, 121 F.3d 1141, 1145 (8th Cir.1997). In Johnson, because the PSR did not give the defendant proper notice of the potential upward departure, the district court itself should have provided the defendant with notice that it was considering departure. Id.
In this case, neither party disputes that the district court itself did not provide advance notice of its intent to depart from the Guidelines to the parties; therefore, the issue is whether the PSR put Hawk Wing on notice that the district court might consider an upward departure. Unlike the PSR in Bums and Johnson, Hawk Wing’s PSR did not expressly state that no factors existed to warrant a departure. While the PSR did not affirmatively recommend an upward departure like the PSR in Andrews and Beatty, it did include a section entitled “Aggravating and Mitigating Circumstances,” which informed Hawk Wing that he had an extensive criminal history for which the PSR assigned no criminal history points. Because the PSR included a specific ground that could form the basis for an upward departure — a criminal history for which no criminal history points were assigned — the notice requirement of Rule 32 was satisfied.
B. Prior Arrests
Hawk Wing also challenges the district court’s reliance, in part, on prior arrests in determining whether to depart upwards. The government responds that even without considering the prior arrests, the district court had ample information before it to justify the upward departure.
[628] A district court is prohibited from considering a prior arrest record itself “for purposes of an upward departure.” U.S.S.G. § 4A1.3(a)(3); United States v. Cammisano, 917 F.2d 1057, 1063 (8th Cir. 1990). However, § 4A1.3(a)(l) of the United States Sentencing Guidelines provides that “[i]f reliable information indicates that the defendant’s criminal history category substantially under-represents the seriousness of the defendant’s criminal history or the likelihood that the defendant will commit other crimes, an upward departure may be warranted.” Thus, a sentencing court may consider prior similar adult criminal conduct not resulting in conviction; prior similar civilly-adjudicated misconduct; and prior sentences, but, a prior arrest record standing alone cannot be considered. United States v. Joshua, 40 F.3d 948, 952-53 (8th Cir.1994).
When the PSR includes the defendant’s arrest record, we and other circuits4 have held that the PSR must also provide specific facts underlying the arrests in order for the arrest record to justify an upward departure; otherwise, the district court may not rely on a mere record of arrest. Id. at 953 (holding that because the district court considered a record of arrest when it departed, the case must be remanded for reconsideration of the sentence). In United States v. Morse, 983 F.2d 851, 854 (8th Cir.1993), the district court departed upward from the Guidelines based on “previous convictions not counted in Morse’s score, pending charges, and the failure of the previous sentences to deter Morse.” With regard to the district court’s consideration of the previous convictions that were not counted in Morse’s criminal history score, we concluded that such reliance on the previous convictions was not error. Id. at 854. In addressing the district court’s reliance on Morse’s pending charges in imposing an upward departure, this court noted that “[ojther circuits have recognized that courts may consider pending charges or uncharged conduct in its determination of a defendant’s accurate criminal history.” Id. This court explained, however, that “[e]ven without considering the two pending charges against Morse, the district court had adequate grounds to depart under § 4A1.3.” Id. Thus, the court concluded that while “unproven charges are not a solid basis for enhancement ... such unproven charges are, under the circumstances of this case, including the defendant’s background, more than ample to warrant the departure taken.” Id. at 854-55.
We hold the district court did not err in considering Hawk Wing’s guilty pleas. Just as the district court in Morse could properly rely on previous convictions not counted in the defendant’s criminal history score, so too could the district [629] court in this case rely on prior charges for which Hawk Wing pleaded guilty. Because Hawk Wing failed to object to the inclusion of the guilty pleas in the PSR, we deem those facts admitted. United States v. Paz, 411 F.3d 906, 909 (8th Cir.2005).
However, the district court could not properly rely on the four active warrants against Hawk Wing stemming from four prior arrests because the PSR did not set forth the factual details underlying the charges. Therefore, under Morse, we must determine whether the district court would have imposed the same sentence had it not relied upon the pending charges. Unlike the district court in Joshua, the district court did not solely rely on Hawk Wing’s prior arrests in departing upward; instead, it also cited Hawk Wing’s juvenile adjudications and seven additional adult convictions to justify the upward departure. Thus, we conclude that the district court had adequate grounds to depart upward despite its error in considering the prior arrests for which the PSR did not set forth the factual details.
C. Improper Incarceration
Hawk Wing also argues that the district court’s statement that “incarceration will provide [Hawk Wing] with needed educational and vocational training, medical care, and other correctional treatment in the most effective manner” was directly contrary to the statutory prohibition against using imprisonment to promote rehabilitation as set forth in 18 U.S.C. § 3582 and 28 U.S.C. § 944(k). We disagree.
When determining the appropriate term of imprisonment, courts should recognize that “imprisonment is not an appropriate means of promoting correction and rehabilitation.” 18 U.S.C. § 3582. Thus, Congress required the Federal Sentencing Commission to “insure that the guidelines reflect the inappropriateness of imposing a sentence to a term of imprisonment for the purpose of rehabilitating the defendant or providing the defendant with needed educational or vocational training, medical care, or other correctional treatment.” 28 U.S.C. § 994(k). Because of the prohibitive language in § 3852 and § 994(k), “other circuits have recognized ... when imposing an original sentence to a term of imprisonment, it is inappropriate for the district court to consider rehabilitation of the defendant as the sole purpose for imprisonment.” United States v. Tsosie, 376 F.3d 1210, 1214 (10th Cir.2004) (citing United States v. Brown, 224 F.3d 1237, 1240 (11th Cir.2000)); United States v. Jackson, 70 F.3d 874, 879 (6th Cir.1995).5
While the district court must acknowledge that imprisonment is not an appropriate means to promote rehabilitation, it must consider, for sentencing purposes, the need for the sentence imposed to provide the defendant “with needed educational or vocational training, medical care, or other correctional treatment in the most effective manner.” United States v. Jasper, 338 F.3d 865, 867 (8th Cir.2003) (comparing § 3852(a) with § 3553(a)(2)); United States v. Holmes, 283 F.3d 966, 968 (8th Cir.2002) (comparing § 3852(a) with § 3553(a)(2)). See also United States v. Hardy, 101 F.3d 1210, 1212-13 (7th Cir. 1996) (stating that when a district judge is [630] sentencing a defendant within the Guidelines range, it is instructed by § 3553(a)(2)(D) to consider educational, medical, and other correctional needs); United States v. Anderson, 15 F.3d 278, 281 (2d Cir.1994) (stating that § 3582(a) refers district courts to factors set forth in § 3553(a)(2)(D)).
The Sixth Circuit explained the interplay between § 3852(a) and § 3553(a)(2)(D) as follows:
For purposes of initial sentencing, a court may not consider rehabilitative goals in considering whether to impose a sentence of imprisonment. However, it may consider rehabilitative goals in determining whether to sentence a defendant within a particular guideline range. Although it is difficult to see a distinction between the imposition of a sentence of imprisonment and the length of imprisonment, the statutory scheme does suggest that rehabilitative needs are relevant to the determination of the length of a sentence.
Jackson, 70 F.3d at 879-80, 880 n. 6 (emphasis added) (internal citations omitted). Thus, after the district court chooses imprisonment as a proper punishment, it is not prohibited under § 3582 from considering correction and rehabilitation in determining the length of the imprisonment. Duran, 37 F.3d at 561 n. 3.6
We conclude the district court did not improperly consider rehabilitative goals in violation § 3852. Neither the parties nor the district court ever discussed the possibility of Hawk Wing receiving probation instead of a term of imprisonment. Instead, the district court had already determined that Hawk Wing’s placement in a criminal history Category IV subjected him to a range of six to twelve months of incarceration. Only after determining that Hawk Wing would receive a sentence of imprisonment did the district court consider the § 3553(a)(2)(D) factor of rehabilitation in deciding the appropriate length of the sentence. At sentencing, the district court directly quoted § 3553(a)(2)(D) in explaining its reasons for an upward departure. Because the district court considered § 3553(a)(2)(D) in determining the length of the sentence of incarceration rather than whether to incarcerate, we find no error.
D. Criminal History
Lastly, Hawk Wing argues that because the district court established his criminal history category at Category IV instead of Category III, it was precluded from any further upward departure based upon an inadequacy of criminal history. In addition, Hawk Wing argues that the district court’s sentence is unreasonable under the 18 U.S.C. § 3553(a) factors.
Section 4A1.3(a)(l) of the United States Sentencing Guidelines provides that “[i]f reliable information indicates that the defendant’s criminal history category substantially under-represents the seriousness of the defendant’s criminal history or the likelihood that the defendant will commit other crimes, an upward departure may be warranted.” When imposing an upward departure under § 4A1.3(a)(l), the sentencing court “first must proceed along the criminal history axis of the sentencing matrix, comparing the defendant’s criminal [631] history with the criminal histories of other offenders in each higher category.” LeCompte, 99 F.3d at 280 (citing United States v. Day, 998 F.2d 622, 625 (8th Cir. 1993)). If the court arrives at Category VI, the highest criminal history category, and determines that the sentencing range remains inadequate, then it “may impose a reasonable sentence above the Category VI range.” Id. (citing Day, 998 F.2d at 625). While the sentencing court does not have to mechanically discuss each criminal history category it rejects, the court must adequately explain and support the upward departure. Id. (citing Day, 998 F.2d at 625); United States v. Thornberg, 326 F.3d 1023, 1027 (8th Cir.2003) (citing United States v. Collins, 104 F.3d 143, 145 (8th Cir.1997)).
Since United States v. Booker, 543 U.S. 220, 245, 125 S.Ct. 738, 757, 160 L.Ed.2d 621 (2005), which declared the Federal Sentencing Guidelines to be advisory, our circuit has urged district courts to follow a three-step sentencing approach. Haack, 403 F.3d at 1002 (citing United States v. Crosby, 397 F.3d 103, 113 (2d Cir.2005)). First, the sentencing court must “determine the appropriate guidelines sentencing range, since that range does remain an important factor to be considered in the imposition of a sentence.” Id. at 1003. When determining the appropriate sentencing range, the district court should identify potential sentencing ranges, the reason why the court is not choosing a specific range, and other § 3553(a) factors. Id. The district court should not “determine the sentence in any manner other than the way the sentence would have been determined pre-Booker.” Id. Second, after determining the appropriate sentencing range, the district court must decide if a “traditional departure” is appropriate under Part K or § 4A1.3. Id. at 1003. Finally, after the district court determines the Guidelines sentence, it must consider “all other factors in § 3553(a) to determine whether to impose the sentence under the guidelines or a non-guidelines sentence.” Id. When a court of appeals reviews a district court’s sentencing determination for reasonableness, “the correct guidelines range is still ‘the critical starting point for the imposition of a sentence.’ ” United States v. Hadash, 408 F.3d 1080, 1082 (8th Cir.2005) (citing United States v. Mashek, 406 F.3d 1012(8th Cir.2005)).
If the parties do not dispute the applicable Sentencing Guidelines range, then the appellate court must determine “whether the sentence imposed is a reasonable ‘guidelines sentence’ and, if not, whether there are other factors under § 3553(a) that would make the sentence reasonable.” Id. “Reasonableness as a constraint on a district court’s discretion to depart ... infers a limited range of choice.” Id. at 1004. A district court’s discretionary sentencing determination may be unreasonable if it does not consider “a relevant factor that should have received significant weight, gives significant weight to an improper or irrelevant factor, or considers only appropriate factors but nevertheless commits a clear error of judgment by arriving at a sentence outside the limited range of choice dictated by the facts of the case.” Id. Thus, an appellate court must determine “whether the sentence, as imposed, is a reasonable ‘non-guidelines sentence’ applying the ... § 3553(a) factors.” Id. at 1006.
Here, Hawk Wing’s argument is not that the district court’s criminal history increase from a Category III to a Category IV violated LeCompte. Instead, Hawk Wing asserts that once the district court placed him in a Category IV with a sentencing range of 6 to 12 months, it could not impose an even higher eighteen-month [632] “non-guideline” sentence because it did not examine whether a sentence under Category V or Category VI would be appropriate. Hawk Wing, however, ignores the three-step approach to determining a sentence that this court set forth in Haack. Hawk Wing fails to assert that the district court selected an inappropriate Guidelines sentencing range or misapplied “traditional departure” rules to arrive at a Guidelines sentence of 6 to 12 months under Category IV.
Because Hawk Wing only challenges what the district court referred to as a “non-guideline sentence” of 18 months, this court must determine whether the “non-guideline” sentence was reasonable in light of the § 3553(a) factors. The district court, in calculating Hawk Wing’s sentence, followed our procedure in Haack by considering the § 3553(a) factors. First, the district court considered “the nature and circumstances of the offense and the history and characteristics of the defendant” under § 3553(a)(1) by “not[ing] that the charge ... involved essentially the theft of various tools and personal property, not high in value but approximately $1,700 in value.” In addition, the district court stated that it “has set forth specifically the history and characteristics of [Hawk Wing] and that history and characteristics] speak for itself.” Second, the district court considered the need for the defendant’s sentence to “reflect the seriousness of the offense, promote respect for the law, and to provide just punishment for the offense” under § 3553(a)(2)(A) and the need for the sentence “to afford adequate deterrence to criminal conduct” under § 3553(a)(2)(B). The district court was “of the abiding feeling that the defendant, by reason of his past history, cannot be deterred from further criminal conduct.” Finally, the district court considered whether the sentence imposed would “provide the defendant with needed educational or vocational training, medical care, or other correctional treatment in the most effective manner” under § 3553(a)(2)(D). Regarding this factor, the district court stated, “[b]y the defendant’s own admission he is an alcoholic and incarceration is reflected by the Court’s sentence and will assist with providing him with needed education or vocational training, medical care, or other corrections treatment in the most effective manner.”
Based on the district court’s thorough analysis of the § 3553(a) factors in determining Hawk Wing’s sentence and our review of that analysis, we cannot say that the sentence imposed is unreasonable. Accordingly, we affirm the judgment of the district court.